Split packing: packing circles into triangles with optimal worst-case density. (English) Zbl 1491.68258
Ellen, Faith (ed.) et al., Algorithms and data structures. 15th international symposium, WADS 2017, St. John’s, NL, Canada, July 31 – August 2, 2017. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10389, 373-384 (2017).
Summary: In the circle packing problem for triangular containers, one asks whether a given set of circles can be packed into a given triangle. Packing problems like this have been shown to be \(\mathsf {NP}\)-hard. In this paper, we present a new sufficient condition for packing circles into any right or obtuse triangle using only the circles’ combined area: it is possible to pack any circle instance whose combined area does not exceed the triangle’s incircle. This area condition is tight, in the sense that for any larger area, there are instances which cannot be packed.
A similar result for square containers has been established earlier this year, using the versatile, divide-and-conquer-based split packing algorithm. In this paper, we present a generalized, weighted version of this approach, allowing us to construct packings of circles into asymmetric triangles. It seems crucial to the success of these results that split packing does not depend on an orthogonal subdivision structure. Beside realizing all packings below the critical density bound, our algorithm can also be used as a constant-factor approximation algorithm when looking for the smallest non-acute triangle of a given side ratio in which a given set of circles can be packed.
An interactive visualization of the Split Packing approach and other related material can be found at https://morr.cc/split-packing/.
For the entire collection see [Zbl 1369.68023].
A similar result for square containers has been established earlier this year, using the versatile, divide-and-conquer-based split packing algorithm. In this paper, we present a generalized, weighted version of this approach, allowing us to construct packings of circles into asymmetric triangles. It seems crucial to the success of these results that split packing does not depend on an orthogonal subdivision structure. Beside realizing all packings below the critical density bound, our algorithm can also be used as a constant-factor approximation algorithm when looking for the smallest non-acute triangle of a given side ratio in which a given set of circles can be packed.
An interactive visualization of the Split Packing approach and other related material can be found at https://morr.cc/split-packing/.
For the entire collection see [Zbl 1369.68023].
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 52C15 | Packing and covering in \(2\) dimensions (aspects of discrete geometry) |
| 68W25 | Approximation algorithms |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Software:
Split PackingReferences:
| [1] | Brubach, B.; Bampis, E.; Svensson, O., Improved bound for online square-into-square packing, Approximation and Online Algorithms, 47-58, 2015, Cham: Springer, Cham · Zbl 1410.68405 |
| [2] | Castillo, I.; Kampas, FJ; Pintér, JD, Solving circle packing problems by global optimization: numerical results and industrial applications, European Journal of Operational Research, 191, 3, 786-802, 2008 · Zbl 1156.90013 · doi:10.1016/j.ejor.2007.01.054 |
| [3] | Demaine, E.D., Fekte, S.P., Lang, R.J.: Circle packing for origami design is hard. In: 5th International Conference on Origami in Science, Mathematics and Education, pp. 609-626. AK Peters/CRC Press (2011) |
| [4] | Fekete, SP; Hoffmann, H-F; Raghavendra, P.; Raskhodnikova, S.; Jansen, K.; Rolim, JDP, Online square-into-square packing, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 126-141, 2013, Heidelberg: Springer, Heidelberg · Zbl 1407.68561 · doi:10.1007/978-3-642-40328-6_10 |
| [5] | Fekete, SP; Hoffmann, H-F, Online Square-into-Square Packing, Algorithmica, 77, 3, 867-901, 2017 · Zbl 1364.90288 · doi:10.1007/s00453-016-0114-2 |
| [6] | Fekete, S.P., Morr, S., Scheffer, C.: Split Packing: Algorithms for Packing Circles with Optimal Worst-Case Density. CoRR abs/1705.00924 (2017). http://arxiv.org/abs/1705.00924 |
| [7] | Hifi, M., M’hallah, R.: A literature review on circle and sphere packing problems: models and methodologies. Advances in Operations Research Article ID 150624 (2009) · Zbl 1198.90337 |
| [8] | Hokama, P.; Miyazawa, FK; Schouery, RCS, A bounded space algorithm for online circle packing, Information Processing Letters, 116, 5, 337-342, 2016 · Zbl 1352.68289 · doi:10.1016/j.ipl.2015.12.007 |
| [9] | Lang, R.J.: A computational algorithm for origami design. In: Proceedings of the Twelfth Annual Symposium on Computational Geometry (SoCG), pp. 98-105 (1996) |
| [10] | Locatelli, M.; Raber, U., Packing equal circles in a square: a deterministic global optimization approach, Discrete Applied Mathematics, 122, 1, 139-166, 2002 · Zbl 1019.90033 · doi:10.1016/S0166-218X(01)00359-6 |
| [11] | Miyazawa, FK; Pedrosa, LLC; Schouery, RCS; Sviridenko, M.; Wakabayashi, Y.; Schulz, AS; Wagner, D., Polynomial-time approximation schemes for circle packing problems, Algorithms - ESA 2014, 713-724, 2014, Heidelberg: Springer, Heidelberg · Zbl 1425.68437 |
| [12] | Moon, J.W., Moser, L.: Some packing and covering theorems. In: Colloquium Mathematicae, vol. 17(1), pp. 103-110. Institute of Mathematics, Polish Academy of Sciences (1967) · Zbl 0152.39502 |
| [13] | Morr, S.: 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), pp. 99-109 (2017) · Zbl 1410.68375 |
| [14] | Peikert, R., Würtz, D., Monagan, M., de Groot, C.: Packing circles in a square: A review and new results. In: Proceedings of the 15th IFIP Conference, pp. 45-54 (1992) · Zbl 0789.52002 |
| [15] | Specht, E.: Packomania (2015). http://www.packomania.com/ |
| [16] | Sugihara, K.; Sawai, M.; Sano, H.; Kim, D-S; Kim, D., Disk packing for the estimation of the size of a wire bundle, Japan Journal of Industrial and Applied Mathematics, 21, 3, 259-278, 2004 · Zbl 1126.52300 · doi:10.1007/BF03167582 |
| [17] | Szabó, P.G., Markót, M.C., Csendes, T., Specht, E., Casado, L.G., García, I.: New Approaches to Circle Packing in a Square. Springer, US (2007) · Zbl 1128.52012 |
| [18] | Wang, H.; Huang, W.; Zhang, Q.; Xu, D., An improved algorithm for the packing of unequal circles within a larger containing circle, European Journal of Operational Research, 141, 2, 440-453, 2002 · Zbl 1081.90593 · doi:10.1016/S0377-2217(01)00241-7 |
| [19] | Würtz, D., Monagan, M., Peikert, R.: The history of packing circles in a square. Maple Technical Newsletter, pp. 35-42 (1994) |
| [20] | Yinfeng, X., On the minimum distance determined by \(n(\le 7)\) points in an isoscele right triangle, Acta Mathematicae Applicatae Sinica, 12, 2, 169-175, 1996 · Zbl 0874.52011 · doi:10.1007/BF02007736 |
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.
