Geodesic
Algorithms of optimal ball packing into ellipsoids
Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta, Tome 52 (2018), pp. 59-74.

Voir la notice de l'article provenant de la source Math-Net.Ru

The article deals with the problem of constructing a package from a set of congruent balls into closed convex sets. As the form of containers for packaging, ellipsoids are chosen. In one case, the number of package elements is considered fixed, and the maximization of the radii of package elements is chosen as the optimization criterion. In another case, the radius of the balls is fixed and the problem of finding the package with the largest number of elements is posed. Iterative algorithms for constructing optimal packages based on the imitation of pushing their centers away from each other and from the container boundary are proposed. Algorithms are developed for constructing packages on the basis of the most dense packaging of three-dimensional space, which is a lattice of various types and their combinations. A simulation of the solution of a number of problems and visualization of results is performed.
Keywords: packing, Chebyshev center, super differential, iterative algorithm, face-centered cubic lattice. 
@article{IIMI_2018_52_a4,
     author = {P. D. Lebedev and N. G. Lavrov},
     title = {Algorithms of optimal ball packing into ellipsoids},
     journal = {Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta},
     pages = {59--74},
     publisher = {mathdoc},
     volume = {52},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IIMI_2018_52_a4/}
}
TY  - JOUR
AU  - P. D. Lebedev
AU  - N. G. Lavrov
TI  - Algorithms of optimal ball packing into ellipsoids
JO  - Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta
PY  - 2018
SP  - 59
EP  - 74
VL  - 52
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IIMI_2018_52_a4/
LA  - ru
ID  - IIMI_2018_52_a4
ER  - 
%0 Journal Article
%A P. D. Lebedev
%A N. G. Lavrov
%T Algorithms of optimal ball packing into ellipsoids
%J Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta
%D 2018
%P 59-74
%V 52
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IIMI_2018_52_a4/
%G ru
%F IIMI_2018_52_a4
P. D. Lebedev; N. G. Lavrov. Algorithms of optimal ball packing into ellipsoids. Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta, Tome 52 (2018), pp. 59-74. http://geodesic.mathdoc.fr/item/IIMI_2018_52_a4/

[1] Sloane N. J. A., “The packing of spheres”, Scientific American, 250:1 (1984), 116–125 | DOI

[2] Tóth L. F., Lagerungen in der Ebene, auf der Kugel und im Raum, Springer, Berlin, 1953, x+198 pp. | DOI | MR | Zbl

[3] Krasovskii N. N., Motion control theory, Nauka, M., 1968, 476 pp.

[4] Kurzhanski A. B., “Ellipsoidal calculus for estimation and feedback control”, Systems and control in the twenty-first century, Birkhäuser, Boston, MA, 1997, 229–243 | DOI | MR | Zbl

[5] Lebedev P. D., Uspenskii A. A., “Algorithms of optimal packing construction in a 3-dimensional Euclidian space”, Proceedings of the 47th international youth school-conference «Modern problems in mathematics and its applications», MPMA 2016, CEUR Workshop Proceedings, 1662, 84–93 (in Russian)

[6] Stoyan Yu.G., Yakovlev S. V., Mathematical models and optimization methods of geometric design, Naukova dumka, Kiev, 1986, 266 pp. | MR

[7] Kazakov A. L., Lempert A. A., “An approach to optimization in transport logistics”, Automation and Remote Control, 72:7 (2011), 1398–1404 | DOI | MR | Zbl

[8] Subbotin A. I., Generalized solutions of first-order PDEs, Birkh{ä}user, Boston, 1995, xi+314 pp. | DOI | MR | MR

[9] Dem'yanov V. F., Vasil'ev L.V., Nondifferentiable optimization, Springer, New York, 1985, XVII+452 pp. | MR | MR

[10] Lebedev P. D., Kazakov A. L., “Iterative methods for the construction of planar packings of circles of different size”, Tr. Inst. Mat. Mekh. Ural. Otd. Ross. Akad. Nauk, 24, no. 2, 2018, 141–151 (in Russian) | DOI

[11] Ushakov V. N., Lebedev P. D., Lavrov N. G., “Algorithms of optimal packing construction in ellipse”, Bulletin of the South Ural State University. Series “Mathematical Modelling, Programming and Computer Software”, 10:3 (2017), 67–79 (in Russian) | DOI | Zbl

[12] Garkavi A. L., “On the Chebyshev center and convex hull of a set”, Uspekhi Mat. Nauk, 19:6 (120) (1964), 139–145 (in Russian) | MR | Zbl

[13] Garkavi A. L., The best possible net and the best possible cross-section of a set in a normed space, 39 (1964), 111–132 | DOI | Zbl | Zbl

[14] Stoyan Yu., Yaskov G., Scheithauer G., “Packing of various solid spheres into a parallelepiped”, Central European Journal of Operational Research, 11:4 (2003), 389–407 | MR | Zbl

[15] Liu J., Yao Y., Zheng Yu, Geng H., Zhou G., “An effective hybrid algorithm for the circles and spheres packing problems”, COCOA 2009: Combinatorial Optimization and Applications, Lecture Notes in Computer Science, 5573, Springer, Berlin–Heidelberg, 2009, 135–144 | DOI | MR | Zbl

[16] Lubachevsky B. D., Stillinger F. H., “Geometric properties of random disk packings”, Journal of Statistical Physics, 60:5–6 (1990), 561–583 | DOI | MR | Zbl

[17] Conway J. H., Sloane N. J. A., Sphere packings, lattices and groups, Springer, New York, 1988, xxvii+665 pp. | DOI | MR | MR | Zbl

[18] Barlow W., “Probable nature of the internal symmetry of crystals”, Nature, 29:738 (1883), 186–188 | DOI

[19] Sukharev A. G., Timokhov A. V., Fedorov V. V., A course in optimization methods, Nauka, M., 1986, 326 pp. | MR

[20] Lebedev P. D., The program for calculating the optimal coverage of a hemisphere by a set of spherical segments, The certificate of state registration no. 2015661543, 29.10.2015

[21] Ushakov V. N., Lebedev P. D., “Algorithms of optimal set covering on the planar $\mathbb{R}^2$”, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 26:2 (2016), 258–270 (in Russian) | DOI | MR | Zbl