DOI: https://doi.org/10.26089/NumMet.v17r216

An algorithm of packing congruent circles in a multiply connected set with non-Euclidean metrics

Authors

  • A.L. Kazakov
  • A.A. Lempert
  • H.L. Nguyen

Keywords:

optimal packing of circles
optical-geometric approach
non-Euclidean space
multiply connected domain
numerical method
computational experiment

Abstract

The problem of optimal packing of congruent circles in a bounded set (a container) in a two-dimensional metric space is considered. It is required to find an arrangement of circles in the container such that these circles occupy the largest area of the container as possible. In the case when the space is Euclidean, this problem is well known, but the case of non-Euclidean metrics is studied much worse. However, there are some applied problems leading us to the use of special non-Euclidean metrics. For example, such a situation appears in the infrastructure logistics. Here we consider the optimal packing problem in the case when the container is simply or multiply connected. A special algorithm based on the optical-geometric approach is proposed and implemented. The results of numerical experiments are discussed.

New computational technologies

Downloads

Published

2016-05-03

Issue

Vol. 17 (2016): Issue 2.

Section

Section 1. Numerical methods and applications

Author Biographies

A.L. Kazakov

Matrosov Institute for System Dynamics and Control Theory of SB RAS (IDSTU SB RAS)
• Head of Laboratory

A.A. Lempert

Matrosov Institute for System Dynamics and Control Theory of SB RAS (IDSTU SB RAS)
• Leading Researcher

H.L. Nguyen

Irkutsk National Research Technical University
• PhD Student

References

  1. A. L. Kazakov and P. D. Lebedev, “Algorithms of Optimal Packing Construction for Planar Compact Sets,” Vychisl. Metody Programm. 16, 307-317 (2015).
  2. D. S. Bukharov and A. L. Kazakov, “VIGOLT System for Solving Transport Logistics Optimization Problems,” Vychisl. Metody Programm. 13, 65-74 (2012).
  3. J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer, New York, 1988; Mir, Moscow, 1990).
  4. H. Kellerer, U. Pferschy, and D. Pisinger, Knapsack Problems (Springer, Berlin, 2004).
  5. V. I. Levenshtein, “Boundaries for Packings in n-Dimensional Euclidean Space,” Dokl. Akad. Nauk SSSR 245 (6), 1299-1303 (1979).
  6. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979; Mir, Moscow, 1982).
  7. L. G. Casado, I. Garcia, P. G. Szabó, and T. Csendes, “Packing Equal Circles in a Square II. - New Results for up to 100 Circles Using the TAMSASS-PECS Algorithm,” in Optimization Theory (Kluwer, Dordrecht, 2001), pp. 207-224.
  8. M. C. Markót and T. Csendes, “A New Verified Optimization Technique for the ’Packing Circles in a Unit Square’ Problems,” SIAM J. Optim. 16 (1), 193-219 (2005).
  9. P. G. Szabó and E. Specht, “Packing up to 200 Equal Circles in a Square,” in Models and Algorithms for Global Optimization (Springer, New York, 2007), pp. 141-156.
  10. M. Goldberg, “Packing of 14, 16, 17 and 20 Circles in a Circle,” Math. Mag. 44 (3), 134-139 (1971).
  11. R. L. Graham, B. D. Lubachevsky, K. J. Nurmela, and P. R. J. Östergard, “Dense Packings of Congruent Circles in a Circle,” Discrete Math. 181 (1-3), 139-154 (1998).
  12. B. D. Lubachevsky and R. L. Graham, “Curved Hexagonal Packings of Equal Disks in a Circle,” Discrete Comput. Geom. 18 (2), 179-194 (1997).
  13. E. G. Birgin and J. M. Gentil, “New and Improved Results for Packing Identical Unitary Radius Circles within Triangles, Rectangles and Strips,” Comput. Oper. Res. 37 (7), 1318-1327 (2010).
  14. I. Litvinchev and E. L. Ozuna, “Integer Programming Formulations for Approximate Packing Circles in a Rectangular Container,” Math. Probl. Eng. 2014 (2014).
    doi 10.1155/2014/317697
  15. I. Litvinchev and E. L. Ozuna, “Packing Circles in a Rectangular Container,” in Proc. Int. Congr. on Logistics and Supply Chain, Queretaro, Mexico, October 24-25, 2013 (Mexican Inst. of Transportation, Queretaro, 2013), pp. 24-25.
  16. C. O. López and J. E. Beasley, “A Heuristic for the Circle Packing Problem with a Variety of Containers,” Eur. J. Oper. Res. 214 (3), 512-525 (2011).
  17. C. O. López and J. E. Beasley, “Packing Unequal Circles Using Formulation Space Search,” Comput. Oper. Res. 40 (5), 1276-1288 (2013).
  18. J. P. Pedroso, S. Cunha, and J. N. Tavares, “Recursive Circle Packing Problems,” Int. Trans. Oper. Res. 23 (1-2), 355-368 (2014).
  19. R. Andrade and E. G. Birgin, “Symmetry-Breaking Constraints for Packing Identical Rectangles within Polyhedra,” Optim. Lett. 7 (2), 375-405 (2013).
  20. Sh. I. Galiev and M. S. Lisafina, “Numerical Optimization Methods for Packing Equal Orthogonally Oriented Ellipses in a Rectangular Domain,” Zh. Vychisl. Mat. Mat. Fiz. 53 (11), 1923-1938 (2013) [Comput. Math. Math. Phys. 53 (11), 1748-1762 (2013)].
  21. H. S. M. Coxeter, “Arrangements of Equal Spheres in Non-Euclidean Spaces,” Acta Math. Acad. Sci. Hung. 5 (3), 263-274 (1954).
  22. K. Böröczky, “Packing of Spheres in Spaces of Constant Curvature,” Acta Math. Acad. Sci. Hung. 32 (3), 243-261 (1978).
  23. J. Szirmai, “The Optimal Ball and Horoball Packings of the Coxeter Tilings in the Hyperbolic 3-Space,” Beitr. Algebra Geom. 46 (2), 545-558 (2005).
  24. J. Szirmai, “The Optimal Ball and Horoball Packings to the Coxeter Honeycombs in the Hyperbolic d-Space,” Beitr. Algebra Geom. 48 (1), 35-47 (2007).
  25. J. Szirmai, “A Candidate for the Densest Packing with Equal Balls in Thurston Geometries,” Beitr. Algebra Geom. 55 (2), 441-452 (2014).
  26. A. L. Kazakov, M. A. Zhuravskaya, and A. A. Lempert, “The Problems of Logistic Platforms Segmentation in the Conditions of Regional Logistics Development,” Transport Urala, No. 4, 17-20 (2010).
  27. A. A. Lempert, A. L. Kazakov, and D. S. Bukharov, “Mathematical Model and Program System for Solving a Problem of Logistic Objects Placement,” Upravlenie Bol’shimi Sistemami, No. 41, 270-284 (2013).
  28. A. L. Kazakov, A. A. Lempert, and D. S. Bukharov, “On Segmenting Logistical Zones for Servicing Continuously Developed Consumers,” Avtom. Telemekh., No. 6, 87-100 (2013) [Autom. Rem. Contr. 74 (6), 968-977 (2013)].
  29. A. L. Kazakov and A. A. Lempert, “An Approach to Optimization in Transport Logistics,” Avtom. Telemekh., No. 7, 50-57 (2011) [Autom. Rem. Contr. 72 (7), 1398-1404 (2011)].
  30. A. L. Kazakov and A. A. Lempert, “On Mathematical Models for Optimization Problem of Logistics Infrastructure,” Int. J. Artif. Intell. 13 (1), 200-210 (2015).
  31. F. P. Preparata and M. I. Shamos, Computational Geometry: An Introduction (Springer, New York, 1985; Mir, Moscow, 1989).
  32. E. Specht, “Packomania,”
    http://www.packomania.com . Cited May 14, 2016.
  33. E. D. Moskalensky, “On Finding Exact Solutions of the Two-Dimensional Eikonal Equation when the Front of the Wave Propagating in a Medium is a Circle,” Sib. Zh. Vychisl. Mat. 17 (4), 363-372 (2014) [Numer. Anal. Appl. 7 (4), 304-313 (2014)].