ALGORITHMS OF OPTIMAL PACKING CONSTRUCTION IN ELLIPSE
DOI:
https://doi.org/10.14529/mmp170306Keywords:
packing, Hausdorff distance, maximization, Chebyshev center, direction derivativeAbstract
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.References
Krasovskii N.N., Subbotin A.I. Pozicionnye differencialnye igry [Positional Differential
Games]. Moscow, Nauka, 1974. 456 p.
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, 2014,
vol. 20, no. 4, pp. 277–286. (in Russian)
Kurzhanski A.B., Valyi I. Ellipsoidal Calculus for Estimation and Control. Basel, Birkh¨auser,
Sloane N.J.A. The Packing of Spheres. Scientific American, 1984, vol. 250, no. 1, pp. 116–125.
DOI: 10.1038/scientificamerican0584-116
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, 2015,
no. 291 (S1), pp. 222–238. DOI: 10.1134/S0081543815090151
Kazakov A.L., Lebedev P.D. Algorithms of Optimal Packing Construction for Planar
Compact Sets. Numerical Methods and Programming, 2015, vol. 16, no. 3, pp. 307–317. (in
Russian)
Dem’yanov V.F., Vasil’ev L.V. Nondifferentiable Optimization. N.Y., Springer, 1985.
DOI: 10.1007/978-1-4613-8268-3
Dem’yanov V.F., Rubinov A.M. Osnovy negladkogo analiza i kvazidifferencialnoe ischislenie
[Foundations of Nonsmooth Analysis and Quasi-Differential Calculus]. Moscow, Nauka, 1990.
Sukharev A.G., Timokhov A.V., Fedorov V.V. Kurs metodov optimizatsii [A Course in
Optimization Methods]. Moscow, Nauka, 1986.
Leichtweiss K. Konvexe Mengen. Berlin, Springer, 1980. DOI: 10.1007/978-3-642-95335-4
Szab´o P.G., Specht E. Packing up to 200 Equal Circles in a Square. Models and Algorithms for
Global Optimization, N.Y., Springer, 2007, pp. 141–156. DOI: 10.1007/978-0-387-36721-7_9
Garkavi A.L. On the Chebyshev Center and Convex Hull of a Set. Russian Mathematical
Surveys, 1964, vol. 19, no. 6, pp. 139–145. (in Rissian)
Belobrov P.K. On the Chebyshev Center of a Set. Russian Mathematics (Izvestiya VUZ.
Matematika), 1964, no. 1 (38), pp. 3–9. (in Russian)
T¨oth L.F. Lagerungen in der Ebene, auf der Kugel und im Raum. Berlin, Springer, 1957.
Graham R.L., Lubachevsky B.D., Nurmela K.J., Osterg˚ard P.R.J. Dense Packings of ¨
Congruent Circles in a Circle. Discrete Mathematics, 1998, vol. 181, no. 1-3, pp. 139–154.
DOI: 10.1016/S0012-365X(97)00050-2
Lubachevsky B.D., Graham R.L. Curved Hexagonal Packings of Equal Disks in a Circle.
Discrete and Computational Geometry, 1997, vol. 18, no. 2, pp. 179–194.
Mark´ot M.Cs., Csendes T.A. A New Verified Optimization Technique for the "Packing Circles
in a Unit Square" Problems. SIAM Journal on Optimization, 2005, vol. 16, no. 1, pp. 193–219.
DOI: 10.1137/S1052623403425617
Goldberg M. Packing of 14, 16, 17 and 20 Circles in a Circle. Mathematics Magazine, 1971,
vol. 44, no. 3, pp. 134–139. DOI: 10.2307/2688222
Chen K., Giblin P. J., Irving A. Mathematical Explorations with MATLAB. N.Y., Cambridge
University Press, 1999. DOI: 10.1017/CBO9780511624117
Erich’s Packing Center. Available at: www2.stetson.edu (accessed May 10, 2017).
