The problem of an optimal packing of incongruent balls into a convex compact set is studied. We consider sets of balls whose radii are proportional to a specified parameter r. The aim is to maximize r. The maximum possible number of different types of balls is three. The problem belongs to the class of NP-hard problems and is solved numerically. We propose algorithms based on partitioning the given compact set into zones of influence of the centers of the elements (generalized Dirichlet zones). The partition is constructed using the optical-geometric approach developed by the authors earlier. A preliminary result is obtained and then improved by a geometric algorithm based on a step-by-step shift of points aimed at maximizing the radius of the current ball. To find the shift direction, we construct the superdifferential of the function equal to the maximum radius of a packed ball centered at the current point. We derive a formula for the maximum growth direction of this function. The developed algorithms are implemented as a software complex for the construction of a ball packing of a compact set. A numerical experiment was carried out for several examples. Packings with balls of different radii are constructed for containers of different shapes: a cube, a sphere, and a cylinder.
Keywords: packing, sphere, optimization, generalized Dirichlet zone, directional derivative, superdifferential, optical-geometric approach
Received March 6, 2020
Revised May 7, 2020
Accepted May 18, 2020
Funding Agency: P.D. Lebedev’s research is supported by the Russian Science Foundation (project no. 19-11-00105), A.L. Kazakov’s research is supported by the Russian Foundation for Basic Research (project no. 18-07-00604), and A.A.Lempert’s research is supported by the Russian Foundation for Basic Research (project no. 20-010-00724).
Pavel Dmitrievich Lebedev. Cand. Phys.-Math. Sci., Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia, Ural Federal University, 620083 Russia, e-mail: pleb@yandex.ru
Alexander 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
Anna Ananievna Lempert. Cand. Phys.-Math. Sci., Matrosov Institute for System Dynamics and Control Theory, Siberian Branch of the Russian Academy of Sciences, Irkutsk, 664033 Russia, e-mail: lempert@icc.ru
REFERENCES
1. Castillo I., Kampas F.J., Pinter J.D. Solving circle packing problems by global optimization: Numerical results and industrial applications. European J. Operat. Research, 2008, vol. 191, no. 3, pp. 786–802. doi: 10.1016/j.ejor.2007.01.054
2. Harary F., Randolph W., Mezey P.G. A study of maximum unit-circle caterpillars – tools for the study of the shape of adsorption patterns. Discrete Appl. Math., 1996, vol. 67, no. 1–3, pp. 127–135. doi: 10.1016/0166-218X(95)00014-I
3. Wang J. Packing of Unequal Spheres and Automated Radiosurgical Treatment Planning. J. Combin. Optim., 1999, vol. 3, no. 4, pp. 453–463. doi: 10.1023/A:1009831621621
4. Hales T. Cannonballs and Honeycombs. Notices of the American Mathematical Society, 2000, vol. 47, pp. 440–449.
5. Chernov N., Stoyan Yu., Romanova T. Mathematical model and efficient algorithms for object packing problem. Computational Geometry, 2010, vol. 43, no. 5, pp. 535–553. doi: 10.1016/j.comgeo.2009.12.003
6. Stoyan Yu.G., Scheithauer G., Yaskov G.N. Packing Unequal Spheres into Various Containers. Cybernetics Syst. Anal., 2016, vol. 52, no. 3, pp. 419–426. doi: 10.1007/s10559-016-9842-1
7. Khlud O.M., Yaskov G.N. Packing homothetic spheroids into a larger spheroid with the jump algorithm. Control, Navigation and Communication Systems, 2017, vol. 6, no. 46, pp. 131–135.
8. Kubach T., Bortfeldt A., Tilli T., Gehring H. Greedy algorithms for packing unequal spheres into a cuboidal strip or a cuboid. Asia Pacific Journal of Operational Research, 2011, vol. 28, no. 6, pp. 739–753. doi: 10.1142/S0217595911003326
9. Huang W.Q., Li Y., Akeb H., Li C.M. Greedy algorithms for packing unequal circles. J. Operat. Research Soc., 2005, vol. 56, no. 5, pp. 539–548. doi: 10.1057/palgrave.jors.2601836
10. Hifi M., Yousef L. Width beam and hill-climbing strategies for the three-dimensional sphere packing problem. In: Annals of Computer Science and Information Systems, vol. 2, Proc. Federated Conference on Computer Science and Information Systems, Warsaw, 2014, pp. 421–428. doi: 10.15439/2014F284
11. Zeng Z.Z., Huang W.Q., Xu R.C., Fu Z.H. An algorithm to packing unequal spheres in a larger sphere. Advanced Materials Research, 2012, vol. 546–547, pp. 1464–1469. doi: 10.4028/www.scientific.net/AMR.546-547.1464
12. Yamada S., Kanno J., Miyauchi M. Multi-sized sphere packing in containers: Optimization formula for obtaining the highest density with two different sized spheres. IPSJ Online Transactions, 2011, vol. 4, pp. 126–133. doi: 10.2197/ipsjtrans.4.126
13. 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).
14. Ushakov V.N., Lebedev P.D., Lavrov N.G. Algorithms of Optimal Packing Construction in Ellipse. Vestnik YuUrGU. Ser. Mat. Model. Progr., 2017, vol. 10, no. 3, pp. 67–79 (in Russian). doi: 10.14529/mmp170306
15. Kazakov A.L. Lempert A.A. Ta T.T. The sphere packing problem into bounded containers in three-dimension non-euclidean space. IFAC PAPERSONLINE, 2018, vol. 51, no. 32, pp. 782–787. doi: 10.1016/j.ifacol.2018.11.450
16. Lebedev P.D., Lavrov N.G. Algorithms of optimal ball packing into ellipsoids. Izv. IMI UdGU, 2018, vol. 52, pp. 59–74 (in Russian). doi: 10.20537/2226-3594-2018-52-05
17. Toth L.F. Regular figures. N Y: A Pergamon Press Book The Macmillan Co., 1964, 339 p. ISBN: 9780080100586 . Translated to Russian under the title Raspolozheniya na ploskosti, na sfere i v prostranstve. Moscow: Fizmatlit Publ., 1958, 365 p.
18. Subbotin A.I. Generalized solutions of first-order PDEs. The dynamical optimization perspective. Basel: Birkhauser, 1995, 314 p. doi: 10.1007/978-1-4612-0847-1 . Translated to Russian under the title Obobshchennye resheniya uravnenii v chastnykh proizvodnykh pervogo poryadka: Perspektivy dinamicheskoi optimizatsii. Moscow; Izhevsk: Inst. Komp’yuter. Issled., 2003, 336 p.
19. 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.
20. Polovinkin E.S., Balashov M.V. Elementy vypuklogo i sil’no vypuklogo analiza [Elements of convex and strongly convex analysis]. Moscow: Fizmatlit Publ., 2004, 416 p. ISBN: 5-9221-0499-3 .
21. Tatarevic M. On limits of dense packing of equal spheres in a cube. arXiv:1503.07933 [cs.CG], 2015, 9 p.
22. Stoyan Y.G., Yaskov, G. Packing congruent hyperspheres into a hypersphere. J. Global Optim., 2012, vol. 52, no. 4, pp. 855–868. doi: 10.1007/s10898-011-9716-z
23. Stoyan Yu.G., Yaskov G. Packing identical spheres into a cylinder. Intern. Trans. Oper. Research, 2010, vol. 17, no. 1, pp. 51–70. doi: 10.1111/j.1475-3995.2009.00733.x
24. Bukharov D.S., Kazakov A.L. VIGOLT system for solving transport logistics optimization problems. Vychisl. Metody Programm., 2012, vol. 13, no. 3, pp. 65–74 (in Russian).
Cite this article as: P.D. Lebedev, A.L. Kazakov, A.A. Lempert. Numerical methods for the construction of packings of different balls into convex compact sets. Trudy Instituta Matematiki i Mekhaniki URO RAN, 2020, vol. 26, no. 2, p p. 173–187.
