Packing Geometric Objects with Optimal Worst-Case Density (Multimedia Exposition)

Authors Aaron T. Becker , Sándor P. Fekete , Phillip Keldenich , Sebastian Morr , Christian Scheffer



PDF
Thumbnail PDF

File

LIPIcs.SoCG.2019.63.pdf
  • Filesize: 1.49 MB
  • 6 pages

Document Identifiers

Author Details

Aaron T. Becker
  • Department of Electrical and Computer Engineering, University of Houston, Houston, TX 77204-4005 USA
Sándor P. Fekete
  • Department of Computer Science, TU Braunschweig, Mühlenpfordtstr. 23, 38106 Braunschweig, Germany
Phillip Keldenich
  • Department of Computer Science, TU Braunschweig, Mühlenpfordtstr. 23, 38106 Braunschweig, Germany
Sebastian Morr
  • Department of Computer Science, TU Braunschweig, Mühlenpfordtstr. 23, 38106 Braunschweig, Germany
Christian Scheffer
  • Department of Computer Science, TU Braunschweig, Mühlenpfordtstr. 23, 38106 Braunschweig, Germany

Cite AsGet BibTex

Aaron T. Becker, Sándor P. Fekete, Phillip Keldenich, Sebastian Morr, and Christian Scheffer. Packing Geometric Objects with Optimal Worst-Case Density (Multimedia Exposition). In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 63:1-63:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.SoCG.2019.63

Abstract

We motivate and visualize problems and methods for packing a set of objects into a given container, in particular a set of {different-size} circles or squares into a square or circular container. Questions of this type have attracted a considerable amount of attention and are known to be notoriously hard. We focus on a particularly simple criterion for deciding whether a set can be packed: comparing the total area A of all objects to the area C of the container. The critical packing density delta^* is the largest value A/C for which any set of area A can be packed into a container of area C. We describe algorithms that establish the critical density of squares in a square (delta^*=0.5), of circles in a square (delta^*=0.5390 ...), regular octagons in a square (delta^*=0.5685 ...), and circles in a circle (delta^*=0.5).

Subject Classification

ACM Subject Classification
  • Theory of computation → Packing and covering problems
  • Theory of computation → Computational geometry
Keywords
  • Packing
  • complexity
  • bounds
  • packing density

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Ignacio Castillo, Frank J. Kampas, and János D. Pintér. Solving circle packing problems by global optimization: numerical results and industrial applications. European Journal of Operational Research, 191(3):786-802, 2008. Google Scholar
  2. Erik D. Demaine, Sándor P. Fekete, and Robert J. Lang. Circle Packing for Origami Design is Hard. In Origami⁵: 5th International Conference on Origami in Science, Mathematics and Education, AK Peters/CRC Press, pages 609-626, 2011. URL: http://arxiv.org/abs/1105.0791.
  3. Sándor P. Fekete, Phillip Keldenich, and Christian. Scheffer. Packing Disks into Disks with Optimal Worst-Case Density. In Proceedings of the 35th Annual Symposium on Computational Geometry (SoCG), LIPIcs, pages 35:1-35:19, 2019. These proceedings; full version at URL: https://arxiv.org/abs/1903.07908.
  4. Sándor P. Fekete, Sebastian Morr, and Christian Scheffer. Split Packing: Algorithms for Packing Circles with Optimal Worst-Case Density. Discrete & Computational Geometry, page 562–594, 2018. URL: http://dx.doi.org/10.1007/s00454-018-0020-2.
  5. F. Fodor. The Densest Packing of 19 Congruent Circles in a Circle. Geometriae Dedicata, 74:139–145, 1999. Google Scholar
  6. F. Fodor. The Densest Packing of 12 Congruent Circles in a Circle. Beiträge zur Algebra und Geometrie (Contributions to Algebra and Geometry), 41:401–409, 2000. Google Scholar
  7. F. Fodor. The Densest Packing of 13 Congruent Circles in a Circle. Beiträge zur Algebra und Geometrie (Contributions to Algebra and Geometry), 44:431–440, 2003. Google Scholar
  8. Hamish J. Fraser and John A. George. Integrated container loading software for pulp and paper industry. European Journal of Operational Research, 77(3):466-474, 1994. Google Scholar
  9. M. Goldberg. Packing of 14, 16, 17 and 20 circles in a circle. Mathematics Magazine, 44:134–139, 1971. Google Scholar
  10. R.L. Graham, B.D. Lubachevsky, K.J. Nurmela, and P.R.J. Östergøard. Dense Packings of Congruent Circles in a Circle. Discrete Mathematics, 181:139–154, 1998. Google Scholar
  11. Mhand Hifi and Rym M'Hallah. A literature review on circle and sphere packing problems: Models and methodologies. Advances in Operations Research, 2009. Article ID 150624. Google Scholar
  12. S. Kravitz. Packing cylinders into cylindrical containers. Mathematics Magazine, 40:65–71, 1967. Google Scholar
  13. Robert J. Lang. A computational algorithm for origami design. Proceedings of the Twelfth Annual Symposium on Computational Geometry (SoCG), pages 98-105, 1996. Google Scholar
  14. Joseph Y. T. Leung, Tommy W. Tam, Chin S. Wong, Gilbert H. Young, and Francis Y. L. Chin. Packing squares into a square. Journal of Parallel and Distributed Computing, 10(3):271–275, 1990. Google Scholar
  15. B.D. Lubachevsky and R.L. Graham. Curved Hexagonal Packings of Equal Disks in a Circle. Discrete & Computational Geometry, 18:179–194, 1997. Google Scholar
  16. H. Melissen. Densest Packing of Eleven Congruent Circles in a Circle. Geometriae Dedicata, 50:15–25, 1994. Google Scholar
  17. John W. Moon and Leo Moser. Some packing and covering theorems. In Colloquium Mathematicae, volume 17, pages 103-110. Institute of Mathematics, Polish Academy of Sciences, 1967. Google Scholar
  18. Sebastian Morr. Split Packing: An Algorithm for Packing Circles with Optimal Worst-Case Density. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 99-109, 2017. Google Scholar
  19. Norman Oler. A finite packing problem. Canadian Mathematical Bulletin, 4:153–155, 1961. Google Scholar
  20. G.E. Reis. Dense Packing of Equal Circles within a Circle. Mathematics Magazine, issue 48:33–37, 1975. Google Scholar
  21. Eckard Specht. Packomania, 2015. URL: http://www.packomania.com/.
  22. Kokichi Sugihara, Masayoshi Sawai, Hiroaki Sano, Deok-Soo Kim, and Donguk Kim. Disk packing for the estimation of the size of a wire bundle. Japan Journal of Industrial and Applied Mathematics, 21(3):259-278, 2004. Google Scholar
  23. Péter Gábor Szabó, Mihaly Csaba Markót, Tibor Csendes, Eckard Specht, Leocadio G. Casado, and Inmaculada García. New Approaches to Circle Packing in a Square. Springer US, 2007. Google Scholar
  24. Huaiqing Wang, Wenqi Huang, Quan Zhang, and Dongming Xu. An improved algorithm for the packing of unequal circles within a larger containing circle. European Journal of Operational Research, 141(2):440–453, September 2002. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail