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

Algorithms of optimal packing construction for planar compact sets

Authors

  • A.L. Kazakov
  • P.D. Lebedev

Keywords:

disk packing
Dirichlet zone
Voronoi diagram
optical geometric method
numerical algorithm
program complex

Abstract

The best packing problem for a prescribed number of equal disks in a compact planar set with their minimally possible radius is considered. An analytical algorithm for constructing the one disk best packing in a polygon in Euclidean space based on the maximization of the distance function from the boundary is proposed. An iteration algorithm based on the previous one is developed using the splitting into subsets (Dirichlet zones) with the aid of the Voronoi diagram. A numerical algorithm for packing in a nonconvex set in non-Euclidian metrics based on the optical geometric analogy is also proposed. A number of examples are numerically solved with a large number of packing elements and for a special non-Euclidian metrics.

New computational technologies

Downloads

Published

2015-06-12

Issue

Vol. 16 (2015): 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

P.D. Lebedev

N.N. Krasovskii Institute of Mathematics and Mechanics of UB RAS (IMM UB RAS)
• Researcher

References

  1. D. S. Bukharov and A. L. Kazakov, “VIGOLT System for Solving Transport Logistics Optimization Problems,” Vychisl. Metody Programm. 13, 65-74 (2012).
  2. A. L. Kazakov and A. A. Lempert, “An Approach to Optimization in Transport Logistics,” Avtom. Telemekh. No. 7, 50-57 (2011) [Autom. Remote Control 72 (7), 1396-1404 (2011)].
  3. V. N. Ushakov, A. R. Matviychuk, and P. D. Lebedev, “Defect of Stability in Game-Pursuit Problem,” Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki No. 3, 87-103 (2010).
  4. P. D. Lebedev and D. S. Bukharov, “Approximation of Polygons with the Best Set of Circles,” Izv. Irkutsk Univ. Ser. Mat. No. 3, 72-87 (2013).
  5. P. D. Lebedev, A. A. Uspenskii, and V. N. Ushakov, “Algorithms of the Best Approximations of the Flat Sets by the Union of Circles,” Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki No. 4, 88-99 (2013).
  6. V. N. Ushakov, A. S. Lakhtin, and P. D. Lebedev, “Optimization of the Hausdorff Distance between Sets in Euclidean Space,” Tr. Inst. Mat. Mekh. UrO RAN 20 (3), 291-308 (2014).
  7. J. H. Conway and N. J. A. Sloane, Sphere Packing, Lattices and Groups (Springer, New York, 1988; Mir, Moscow, 1990).
  8. L. F. Töth, Lagerungen in der Ebene, auf der Kugel und im Raum (Springer, Berlin, 1957; Fizmatlit, Moscow, 1958).
  9. V. I. Levenshtein, “Boundaries for Packings in n-Dimensional Euclidean Space,” Dokl. Akad. Nauk SSSR 245 (6), 1299-1303 (1979).
  10. 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. Remote Control 74 (6), 968-977 (2013)].
  11. A. A. Lempert, A. L. Kazakov, and D. S. Bukharov, “Mathematical Model and Program System for Solving a Problem of Logistic Objects Placement,” in Control of Large Systems (Trapeznikov Inst. Control Sci., Moscow, 2013), Issue 41, pp. 270-284.
  12. P. G. Szabó and E. Specht, “Packing up to 200 Equal Circles in a Square,” in Models and Algorithms for Global Optimization. Optimization and Its Applications (Springer, Heidelberg, 2007), Vol. 4, pp. 141-156.
  13. 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. Applied Optimization (Springer, Heidelberg, 2001), Vol. 59, pp. 207-224.
  14. 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).
  15. C. de Groot, R. Peikert, and D. Würtz, The Optimal Packing of Ten Equal Circles in a Square , Research Report No. 90-12 (Eidgenössische Tech. Hochschule, Zürich, 1990).
  16. 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).
  17. B. D. Lubachevsky and R. L. Graham, “Curved Hexagonal Packings of Equal Disks in a Circle,” Discrete Comput. Geom. 18 (2), 179-194 (1997).
  18. M. Goldberg, “Packing of 14, 16, 17 and 20 Circles in a Circle,” Math. Mag. 44 (3), 134-139 (1971).
  19. K. Leichtweiss, Konvexe Mengen (Springer, Berlin, 1980; Nauka, Moscow, 1985).
  20. V. F. Dem’yanov and L. V. Vasiliev, Nondifferentiated Optimization (Nauka, Moscow, 1981) [in Russian].
  21. B. T. Polyak, Introduction to Optimization (Nauka, Moscow, 1983) [in Russian].
  22. L. M. Mestetsky, Continuous Morphology of Binary Images: Shapes, Frames, Circulars (Fizmatlit, Moscow, 2009) [in Russian].
  23. B. A. Dubrovin, S. P. Novikov, and A. T. Fomenko, Modern Geometry (Fizmatlit, Moscow, 1986) [in Russian].
  24. A. L. Garkavi, “Existence of the Best Net and the Best Width for Set in a Banach Space,” Usp. Mat. Nauk 15 (2), 210-211 (1960).
  25. A. L. Kazakov, A. A. Lempert, and D. S. Bukharov, “On a Numerical Method to Solve Some Optimization Problems Occurring in Transport Logistics,” Vestn. Irkutsk Tekh. Univ. 53 (6), 6-12 (2011).
  26. V. S. Brusov and S. A. Piyavskii, “A Computational Algorithm for Optimally Covering a Plane Region,” Zh. Vychisl. Mat. Mat. Fiz. 11 (2), 304-312 (1971) [USSR Comput. Math. Math. Phys. 11 (2), 17-27 (1971)].
  27. K. Chen, P. J. Giblin, and A. Irving, Mathematical Explorations with MATLAB (Cambridge Univ. Press, New York, 1999; Mir, Moscow, 2001).