Document Open Access Logo

Packing Disks into Disks with Optimal Worst-Case Density

Authors Sándor P. Fekete , Phillip Keldenich , Christian Scheffer

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2019.35.pdf
  • Filesize: 0.99 MB
  • 19 pages

Document Identifiers

Author Details

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
Christian Scheffer
  • Department of Computer Science, TU Braunschweig, Mühlenpfordtstr. 23, 38106 Braunschweig, Germany

Funding

  • Keldenich, Phillip: Supported by the German Research Foundation under Grant No. FE 407/17-2.

Acknowledgements

We thank Sebastian Morr for joint previous work.

Cite AsGet BibTex

Sándor P. Fekete, Phillip Keldenich, and Christian Scheffer. Packing Disks into Disks with Optimal Worst-Case Density. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 35:1-35:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.SoCG.2019.35

Abstract

We provide a tight result for a fundamental problem arising from packing disks into a circular container: The critical density of packing disks in a disk is 0.5. This implies that any set of (not necessarily equal) disks of total area delta <= 1/2 can always be packed into a disk of area 1; on the other hand, for any epsilon>0 there are sets of disks of area 1/2+epsilon that cannot be packed. The proof uses a careful manual analysis, complemented by a minor automatic part that is based on interval arithmetic. Beyond the basic mathematical importance, our result is also useful as a blackbox lemma for the analysis of recursive packing algorithms.

Subject Classification

ACM Subject Classification
  • Theory of computation → Packing and covering problems
  • Theory of computation → Computational geometry
Keywords
  • Disk packing
  • packing density
  • tight worst-case bound
  • interval arithmetic
  • approximation

Metrics

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

Related Versions

Supplementary Materials

References

  1. I. Castillo, F. J. Kampas, and J. 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. E. D. Demaine, S.P. Fekete, and R. 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. P. Fekete, P. Keldenich, and C. Scheffer. Packing Disks into Disks with Optimal Worst-Case Density. Computing Research Repository (CoRR), 2019. URL: http://arxiv.org/abs/1903.07908.
  4. S. P. Fekete, S. Morr, and C. Scheffer. Split Packing: Algorithms for Packing Circles with Optimal Worst-Case Density. Discrete & Computational Geometry, 2018. URL: http://dx.doi.org/10.1007/s00454-018-0020-2.
  5. S. P. Fekete and J. Schepers. New Classes of Fast Lower Bounds for Bin Packing Problems. Math. Program., 91(1):11-31, 2001. Google Scholar
  6. S. P. Fekete and J. Schepers. A General Framework for Bounds for Higher-Dimensional Orthogonal Packing Problems. Math. Methods Oper. Res., 60:311-329, 2004. Google Scholar
  7. F. Fodor. The Densest Packing of 19 Congruent Circles in a Circle. Geometriae Dedicata, 74:139–145, 1999. Google Scholar
  8. 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
  9. 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
  10. H. J. Fraser and J. A. George. Integrated container loading software for pulp and paper industry. European Journal of Operational Research, 77(3):466-474, 1994. Google Scholar
  11. M. Goldberg. Packing of 14, 16, 17 and 20 circles in a circle. Mathematics Magazine, 44:134–139, 1971. Google Scholar
  12. 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
  13. M. Hifi and R. M'hallah. A literature review on circle and sphere packing problems: models and methodologies. Advances in Operations Research, 2009. Article ID 150624. Google Scholar
  14. P. Hokama, F. K. Miyazawa, and R. C. S. Schouery. A bounded space algorithm for online circle packing. Information Processing Letters, 116(5):337–342, May 2016. Google Scholar
  15. S. Kravitz. Packing cylinders into cylindrical containers. Mathematics Magazine, 40:65–71, 1967. Google Scholar
  16. R. J. Lang. A computational algorithm for origami design. Proceedings of the Twelfth Annual Symposium on Computational Geometry (SoCG), pages 98-105, 1996. Google Scholar
  17. J. Y. T. Leung, T. W. Tam, C. S. Wong, G. H. Young, and F. Y. L. Chin. Packing squares into a square. Journal of Parallel and Distributed Computing, 10(3):271–275, 1990. Google Scholar
  18. 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
  19. H. Melissen. Densest Packing of Eleven Congruent Circles in a Circle. Geometriae Dedicata, 50:15–25, 1994. Google Scholar
  20. F. K. Miyazawa, L. L. C. Pedrosa, R. C. S. Schouery, M. Sviridenko, and Y. Wakabayashi. Polynomial-time approximation schemes for circle packing problems. In Proceedings of the 22nd European Symposium on Algorithms (ESA), pages 713-724, 2014. Google Scholar
  21. J. W. Moon and L. Moser. Some packing and covering theorems. In Colloquium Mathematicae, volume 17, pages 103-110. Institute of Mathematics, Polish Academy of Sciences, 1967. Google Scholar
  22. S. 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
  23. N. Oler. A finite packing problem. Canadian Mathematical Bulletin, 4:153–155, 1961. Google Scholar
  24. R. Peikert, D. Würtz, M. Monagan, and C. de Groot. Packing circles in a square: A review and new results. In Proceedings of the 15th IFIP Conference, pages 45-54, 1992. Google Scholar
  25. G.E. Reis. Dense Packing of Equal Circles within a Circle. Mathematics Magazine, issue 48:33–37, 1975. Google Scholar
  26. E. Specht. Packomania, 2015. URL: http://www.packomania.com/.
  27. K. Sugihara, M. Sawai, H. Sano, D.-S. Kim, and D. 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
  28. P. G. Szabó, M. C. Markót, T. Csendes, E. Specht, L. G. Casado, and I. García. New Approaches to Circle Packing in a Square. Springer US, 2007. Google Scholar
  29. H. Wang, W. Huang, Q. Zhangn, and D. 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
  30. D. Würtz, M. Monagan., and R. Peikert. The history of packing circles in a square. Maple Technical Newsletter, page 35–42, 1994. 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact