Packing disks into disks with optimal worst-case density. (English) Zbl 1510.52013
Authors’ 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 \le 1/2\) can always be packed into a disk of area 1; on the other hand, for any \(\varepsilon >0\) there are sets of disks of area \(1/2+\varepsilon\) 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.
Reviewer: Christian Richter (Jena)
MSC:
| 52C15 | Packing and covering in \(2\) dimensions (aspects of discrete geometry) |
| 05B40 | Combinatorial aspects of packing and covering |
| 52C26 | Circle packings and discrete conformal geometry |
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
Keywords:
disk packing; packing density; tight worst-case bound; interval arithmetic; approximation; NP-hardnessSoftware:
Split PackingReferences:
| [1] | Becker, A.T., Fekete, S.P., Keldenich, Ph., Morr, S., Scheffer, Ch.: Packing geometric objects with optimal worst-case density. In: 35th International Symposium on Computational Geometry (Portland 2019). Leibniz Int. Proc. Inform., vol. 129, # 63. Leibniz-Zent. Inform., Wadern (2019). Video available via https://www.youtube.com/watch?v=QpyjB8c4Ngk · Zbl 07559263 |
| [2] | Castillo, I.; Kampas, FJ; Pintér, JD, Solving circle packing problems by global optimization: numerical results and industrial applications, Eur. J. Oper. Res., 191, 3, 786-802 (2008) · Zbl 1156.90013 · doi:10.1016/j.ejor.2007.01.054 |
| [3] | Demaine, E.D., Fekete, S.P., Lang, R.J.: Circle packing for origami design is hard. In: 5th International Meeting on Origami in Science, Mathematics and Education (Singapore 2010), pp. 609-626. CRC Press, Boca Raton (2011) |
| [4] | Fekete, S.P., Keldenich, Ph., Scheffer, Ch.: Packing disks into disks with optimal worst-case density. In: 35th International Symposium on Computational Geometry (Portland 2019). Leibniz Int. Proc. Inform., vol. 129, # 35. Leibniz-Zent. Inform., Wadern (2019) · Zbl 07559235 |
| [5] | Fekete, SP; Morr, S.; Scheffer, Ch, Split packing: algorithms for packing circles with optimal worst-case density, Discrete Comput. Geom., 61, 3, 562-594 (2019) · Zbl 1411.90046 · doi:10.1007/s00454-018-0020-2 |
| [6] | Fodor, F., The densest packing of 19 congruent circles in a circle, Geom. Dedicata, 74, 2, 139-145 (1999) · Zbl 0927.52024 · doi:10.1023/A:1005091317243 |
| [7] | Fodor, F., The densest packing of 12 congruent circles in a circle, Beiträge Algebra Geom., 41, 2, 401-409 (2000) · Zbl 0974.52015 |
| [8] | Fodor, F., The densest packing of 13 congruent circles in a circle, Beiträge Algebra Geom., 44, 2, 431-440 (2003) · Zbl 1039.52015 |
| [9] | Fraser, HJ; George, JA, Integrated container loading software for pulp and paper industry, Eur. J. Oper. Res., 77, 3, 466-474 (1994) · Zbl 0800.90656 · doi:10.1016/0377-2217(94)90410-3 |
| [10] | Goldberg, M., Packing of 14, 16, 17 and 20 circles in a circle, Math. Mag., 44, 3, 134-139 (1971) · Zbl 0212.54504 · doi:10.1080/0025570X.1971.11976122 |
| [11] | Graham, R.L., Lubachevsky, B.D., Nurmela, K.J., Östergård P.R.J.: Dense packings of congruent circles in a circle. Discrete Math. 181(1-3), 139-154 (1998) · Zbl 0901.52017 |
| [12] | Hifi, M., M’hallah, R.: A literature review on circle and sphere packing problems: models and methodologies. Adv. Oper. Res. 2009, # 150624 (2009) · Zbl 1198.90337 |
| [13] | Hokama, P.; Miyazawa, FK; Schouery, RCS, A bounded space algorithm for online circle packing, Inform. Process. Lett., 116, 5, 337-342 (2016) · Zbl 1352.68289 · doi:10.1016/j.ipl.2015.12.007 |
| [14] | Kravitz, S., Packing cylinders into cylindrical containers, Math. Mag., 40, 2, 65-71 (1967) · Zbl 0192.28801 · doi:10.1080/0025570X.1967.11975768 |
| [15] | Lang, R.J.: A computational algorithm for origami design. In: 12th Annual Symposium on Computational Geometry (Philadelphia 1996), pp. 98-105. ACM, New York (1996) |
| [16] | Leung, J.Y.-T., Tam, T.W., Wong, C.S., Young, G.H., Chin, F.Y.L.: Packing squares into a square. J. Parallel Distrib. Comput. 10(3), 271-275 (1990) |
| [17] | Lubachevsky, BD; Graham, RL, Curved hexagonal packings of equal disks in a circle, Discrete Comput. Geom., 18, 2, 179-194 (1997) · Zbl 0881.52010 · doi:10.1007/PL00009314 |
| [18] | Melissen, H., Densest packings of eleven congruent circles in a circle, Geom. Dedicata, 50, 1, 15-25 (1994) · Zbl 0810.52013 · doi:10.1007/BF01263647 |
| [19] | Miyazawa, F.K., Pedrosa, L.L.C., Schouery, R.C.S., Sviridenko, M., Wakabayashi, Y.: Polynomial-time approximation schemes for circle packing problems. In: 22nd European Symposium on Algorithms (Wrocław 2014). Lecture Notes in Comput. Sci., vol. 8737, pp. 713-724. Springer, Heidelberg (2014) · Zbl 1425.68437 |
| [20] | Moon, JW; Moser, L., Some packing and covering theorems, Colloq. Math., 17, 103-110 (1967) · Zbl 0152.39502 · doi:10.4064/cm-17-1-103-110 |
| [21] | Morr, S.: Split packing: an algorithm for packing circles with optimal worst-case density. In: 28th Annual ACM-SIAM Symposium on Discrete Algorithms (Barcelona 2017), pp. 99-109. SIAM, Philadelphia (2017) · Zbl 1410.68375 |
| [22] | Oler, N., A finite packing problem, Can. Math. Bull., 4, 153-155 (1961) · Zbl 0101.40301 · doi:10.4153/CMB-1961-018-7 |
| [23] | Peikert, R., Würtz, D., Monagan, M., de Groot, C.: Packing circles in a square: a review and new results. In: System Modelling and Optimization (Zürich 1991). Lect. Notes Control Inf. Sci., vol. 180, pp. 45-54. Springer, Berlin (1992) · Zbl 0789.52002 |
| [24] | Reis, GE, Dense packing of equal circles within a circle, Math. Mag., 48, 33-37 (1975) · Zbl 0297.52014 · doi:10.1080/0025570X.1975.11976434 |
| [25] | Specht, E.: Packomania (2015). http://www.packomania.com |
| [26] | Sugihara, K.; Sawai, M.; Sano, H.; Kim, D-S; Kim, D., Disk packing for the estimation of the size of a wire bundle, Jpn. J. Ind. Appl. Math., 21, 3, 259-278 (2004) · Zbl 1126.52300 · doi:10.1007/BF03167582 |
| [27] | Szabó, P.G., Markót, M.Cs., Csendes, T., Specht, E., Casado, L.G., García, I.: New Approaches to Circle Packing in a Square. Springer Optimization and Its Applications, vol. 6. Springer, New York (2007) · Zbl 1128.52012 |
| [28] | Wang, H.; Huang, W.; Zhang, Q.; Xu, D., An improved algorithm for the packing of unequal circles within a larger containing circle, Eur. J. Oper. Res., 141, 2, 440-453 (2002) · Zbl 1081.90593 · doi:10.1016/S0377-2217(01)00241-7 |
| [29] | Würtz, D., Monagan, M., Peikert, R.: The history of packing circles in a square. Maple Technical Newsletter, 35-42 (1994) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
