We consider the problem of constructing an optimal packing of a fixed number $n>1$ of circles, generally, of different radii in a planar compact set $M$. It is assumed that a positive number is given for each element of the packing such that the radius of the circle equals the product of this number by a parameter $r$, which is common to the whole package. The optimality criterion is the maximum of $r$, which leads, in particular, to an increase in the packing density, which is the ratio of the area of the packing to the area of $M$. In the proposed solution method, we iteratively change the coordinates of the centers of the packing elements $S_n$, which makes it possible to increase the radii of the circles. The developed computational procedures imitate the repulsion of the center of each element of the packing from nearby centers of other elements and from the boundary of $M$. We study the differential properties of a function of two variables $(x,y)$ whose value is the maximum radius of the circle of the packing centered at the point $(x,y)$, where the centers of the remaining elements are assumed to be fixed. The software implementation employs the notion of Chebyshev center of a compact set. A software complex is created and a number of examples are considered for sets $M$ of different geometry with the use of this complex. The results are visualized.
Keywords: circle packing problem (CPP), optimization, Chebyshev center, superdifferential, iterative algorithm.
The paper was received by the Editorial Office on March 15, 2018.
Funding Agency:
Russian Foundation for Basic Research (Grant Numbers: 18-01-00221, 18-07-00604, 16-06-00464).
Pavel Dmitrievich Lebedev, Cand. Sci. (Phys.-Math.), Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620990 Russia,
e-mail: pleb@yandex.ru
Aleksandr Leonidovich Kazakov, Dr. Phys.-Math. Sci., Matrosov Institute for System Dynamics and Control Theory, Siberian Branch of the Russian Academy of Sciences, Irkutsk, 664033 Russia,
e-mail: kazakov@icc.ru
REFERENCES
1. Krasovskii N.N., Subbotin A.I. Game-theoretical control problems. N Y: Springer, 1987. 517 p. This book is substantially revised version of the monograph Pozitsionnye differentsial’nye igry, Moscow, Nauka Publ., 1974, 456 p.
2. Conway J., Sloane N. Sphere Packing. Lattices and Groups. N Y: Springer Science and Business Media, 1999, 706 p. doi: 10.1007/978-1-4757-2016-7 .
3. Hifi M., M’Hallah R. A literature review on circle and sphere packing problems: Models and methodologies. Advances Oper. Research, 2009, vol. 2009, pp. 1–22. doi: 10.1155/2009/150624 .
4. Kazakov A.L., Lempert A.A. An Approach to optimization in transport logistics. Autom. Remote Control., 2011, vol. 72, no. 7, pp. 1398–1404. doi: 10.1134/S0005117911070071 .
5. Kazakov A., Lempert A. On mathematical models for optimization problem of logistics infrastructure. Intern. J. Artificial Intelligence, 2015, vol. 13, no. 1, pp. 200–210.
6. Kazakov A.L., Lebedev P.D. Algorithms of optimal packing construction for planar compact sets. Vychisl. Metody Programm., 2015, vol. 16, no. 2, pp. 307–317 (in Russian).
7. Lebedev P.D., Uspenskii A.A. Algorithms of optimal packing construction in a 3-dimensional Euclidian space. MPMA 2016 – Proc. 47th Intern. Youth School-Conf. “Modern Problems in Mathematics and its Applications”, CEUR Workshop Proceedings, 2016, vol. 1662, pp. 84–93 (in Russian).
8. Yas’kov G.N., Method of decision of task of packing of different circles with choice of perspective initial points, Збiрник наукових праць Харкiвського нацiонального унiверситету Повiтряних Сил, 2010, №3 (25), pp. 119–122 (in Ukrainian). ISSN 2073-7378А,
9. Lopez C., Beasley J. A formulation space search heuristic for packing unequal circles in a fixed size circular container. European J. Oper. Research, 2016, vol. 251, no. 1, pp. 64–73. doi: 10.1016/j.ejor.2015.10.062 .
10. Kubach T., Bortfeldt A., Gehring H. Parallel greedy algorithms for packing unequal circles into a strip or a rectangle. Central European J. Oper. Research, 2009, vol. 17, no. 4, pp. 461–477. doi: 10.1007/s10100-009-0103-5 .
11. Zeng Z., Yu X., Chen M., Liu Yu. A memetic algorithm to pack unequal circles into a square. Computers Oper. Research, 2018, vol. 92, pp. 47–55. doi: 10.1016/j.cor.2017.09.013 .
12. Kazakov A.L., Lempert A.A., Le Q.M. An algorithm for packing circles of two types in a fixed size container with Non-Euclidean metric. CEUR Workshop Proc., 2017, vol. 1975, pp. 286–297.
13. Subbotin A.I. Generalized solutions of first-order PDEs. The dynamical optimization perspective. Boston: BirkhЈauser, 1995, 312 p. ISBN 978-1-4612-0847-1 . Translated to Russian under the title Obobshchennye resheniya uravnenii v chastnykh proizvodnykh pervogo poryadka. Perspektivy dinamicheskoi optimizatsii. Moscow; Izhevsk: Institut Komp’yuternykh Tekhnologii Publ., 2003, 336 p.
14. Dem’yanov V.F., Vasil’ev L.V. Nondifferentiable optimization. N Y: Springer-Verlag, 1985, 452 p. ISBN: 978-0-387-90951-6 . Original Russian text published in Dem’yanov V.F. Vasil’ev L.V. Nedifferentsiruemaya optimizatsiya. Moscow: Nauka Publ., 1981, 384 p.
15. Dem’yanov V.F., Rubinov A.M. Foundations of Nonsmooth Analysis and Quasi-Differential Calculus (Osnovy negladkogo analiza i kvazidifferentsial’noe ischislenie). Moscow: Nauka Publ., 1990, 432 p. ISBN: 5-02-014241-7 .
16. Sukharev A.G., Timokhov A.V., and Fedorov V.V. Kurs metodov optimizatsii [Course of optimization methods]. Moscow: Nauka Publ., 1986, 326 p. ISBN(2nd ed.): 978-5-9221-0559-0 .
17. Leichtweiss K. Konvexe Mengen. Berlin: Springer, 1980, 330 p. ISBN: 978-3-540-09071-7 . Translated to Russian under the title Vypuklye mnozhestva. Moscow: Nauka Publ., 1985, 335 p.
18. Garkavi A.L. On the Chebyshev center and convex hull of a set. Uspekhi Mat. Nauk., 1964, vol. 19, no. 6 (120), pp. 139–145 (in Russian).
19. T$\ddot{\mathrm{o}}$th L.F. Lagerungen in der Ebene, auf der Kugel und im Raum. Berlin: Springer, 1953, 197 p. ISBN(2nd ed.): 3540054774 . Translated to Russian under the title Raspolozheniya na ploskosti, na sfere i v prostranstve. Moscow: Gos. Izd. Fiz.-Mat. Lit., 1958, 365 p.
