Geodesic
Algorithms of optimal packing construction in ellipse
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, Tome 10 (2017) no. 3, pp. 67-79 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

It is often necessary to realize an approximation of sets with the union of congruent elements in the theory of control. One way for this approximation is a packing of the union of disks with equal radii into a planar figure. Two versions of an optimal packing problem are considered in the present paper: the number of elements is fixed and to maximize their radii is required in one, the radius is fixed and to maximize the number of elements is required in another one. Iterative methods imitating their centers repulsing from each other and from the boarder are applied in the first version. Constructions of the Chebyshev center, orthogonal projections and points repulsing are used for them. Packing with a hexagonal pattern (closed to optimal) is considered in the second version. Software complex for packing into eclipses with different ratio of axes is developed.
Keywords: packing; Hausdorff distance; maximization; Chebyshev center; direction derivative. 
@article{VYURU_2017_10_3_a5,
     author = {V. N. Ushakov and P. D. Lebedev and N. G. Lavrov},
     title = {Algorithms of optimal packing construction in ellipse},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a, Matemati\v{c}eskoe modelirovanie i programmirovanie},
     pages = {67--79},
     year = {2017},
     volume = {10},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VYURU_2017_10_3_a5/}
}
TY  - JOUR
AU  - V. N. Ushakov
AU  - P. D. Lebedev
AU  - N. G. Lavrov
TI  - Algorithms of optimal packing construction in ellipse
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
PY  - 2017
SP  - 67
EP  - 79
VL  - 10
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/VYURU_2017_10_3_a5/
LA  - ru
ID  - VYURU_2017_10_3_a5
ER  - 
%0 Journal Article
%A V. N. Ushakov
%A P. D. Lebedev
%A N. G. Lavrov
%T Algorithms of optimal packing construction in ellipse
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
%D 2017
%P 67-79
%V 10
%N 3
%U http://geodesic.mathdoc.fr/item/VYURU_2017_10_3_a5/
%G ru
%F VYURU_2017_10_3_a5
V. N. Ushakov; P. D. Lebedev; N. G. Lavrov. Algorithms of optimal packing construction in ellipse. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, Tome 10 (2017) no. 3, pp. 67-79. http://geodesic.mathdoc.fr/item/VYURU_2017_10_3_a5/

[1] Krasovskii N. N., Subbotin A. I., Positional Differential Games, Nauka, M., 1974, 456 pp.

[2] Ushakov V. N., Lavrov N. G., Ushakov A. V., “Construction of Solutions in a Problem on the Approach of a Stationary Control System”, Trudy Instituta matematiki i mekhaniki, 20, no. 4 (2014), 277–286 (in Russian)

[3] A.B. Kurzhanski, I. Valyi, Ellipsoidal Calculus for Estimation and Control, Birkhäuser, Basel, 1997 | MR | Zbl

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

[5] Ushakov V. N., Lebedev P. D., Lakhtin A. S., “Optimization of the Hausdorff Distance between Sets in Euclidean Space”, Proceedings of the Steklov Institute of Mathematics, 291, S1 (2015), 222–238 | DOI | MR

[6] Kazakov A. L., Lebedev P. D., “Algorithms of Optimal Packing Construction for Planar Compact Sets”, Numerical Methods and Programming, 16:3 (2015), 307–317 (in Russian)

[7] Dem'yanov V. F., Vasil'ev L.V., Nondifferentiable Optimization, Springer, N.Y., 1985 | DOI | MR

[8] Dem'yanov V. F., Rubinov A. M., Foundations of Nonsmooth Analysis and Quasi-Differential Calculus, Nauka, M., 1990

[9] Sukharev A. G., Timokhov A. V., Fedorov V. V., A Course in Optimization Methods, Nauka, M., 1986

[10] Leichtweiss K., Konvexe Mengen, Springer, Berlin, 1980 | DOI | MR | Zbl

[11] P. G. Szabó, E. Specht, “Packing up to $200$ equal circles in a square”, Models and Algorithms for Global Optimization, Springer, N.Y., 2007, 141–156 | DOI | MR | Zbl

[12] Garkavi A. L., “On the Chebyshev Center and Convex Hull of a Set”, Russian Mathematical Surveys, 19:6 (1964), 139–145 (in Rissian) | Zbl

[13] Belobrov P. K., “On the Chebyshev Center of a Set”, Russian Mathematics (Izvestiya VUZ. Matematika), 1964, no. 1(38), 3–9 (in Russian)

[14] Töth L. F., Lagerungen in der Ebene, auf der Kugel und im Raum, Springer, Berlin, 1957 | MR

[15] R. L. Graham, B. D. Lubachevsky, K. J. Nurmela, P. R. J. Östergård, “Dense Packings of Congruent Circles in a Circle”, Discrete Mathematics, 181:1–3 (1998), 139–154 | DOI | MR | Zbl

[16] B. D. Lubachevsky, R. L. Graham, “Curved Hexagonal Packings of Equal Disks in a Circle”, Discrete Computational Geometry, 18:2 (1997), 179–194 | DOI | MR | Zbl

[17] M. Cs. Markót, T. A. Csendes, “A New Verified Optimization Technique for the “Packing Circles in a Unit Square” Problems”, SIAM Journal on Optimization, 16:1 (2005), 193–219 | DOI | MR | Zbl

[18] M. Goldberg, “Packing of 14, 16, 17 and 20 Circles in a Circle”, Mathematics Magazine, 44:3 (1971), 134–139 | DOI | MR | Zbl

[19] Chen K., Giblin P. J., Irving A., Mathematical Explorations with MATLAB, Cambridge University Press, N.Y., 1999 | DOI | MR | Zbl

[20] (accessed May 10, 2017)