Algorithms of Optimal Packing Construction in Ellipse

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.

References

1. Krasovskii N.N., Subbotin A.I. Pozicionnye differencialnye igry [Positional Differential Games]. Moscow, Nauka, 1974. 456 p.
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, 2014, vol. 20, no. 4, pp. 277-286. (in Russian)
3. Kurzhanski A.B., Valyi I. Ellipsoidal Calculus for Estimation and Control. Basel, Birkhauser, 1997.
4. Sloane N.J.A. The Packing of Spheres. Scientific American, 1984, vol. 250, no. 1, pp. 116-125. DOI: 10.1038/scientificamerican0584-116
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, 2015, no. 291 (S1), pp. 222-238. DOI: 10.1134/S0081543815090151
6. 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)
7. Dem'yanov V.F., Vasil'ev L.V. Nondifferentiable Optimization. N.Y., Springer, 1985. DOI: 10.1007/978-1-4613-8268-3
8. Dem'yanov V.F., Rubinov A.M. Osnovy negladkogo analiza i kvazidifferencialnoe ischislenie [Foundations of Nonsmooth Analysis and Quasi-Differential Calculus]. Moscow, Nauka, 1990.
9. Sukharev A.G., Timokhov A.V., Fedorov V.V. Kurs metodov optimizatsii [A Course in Optimization Methods]. Moscow, Nauka, 1986.
10. Leichtweiss K. Konvexe Mengen. Berlin, Springer, 1980. DOI: 10.1007/978-3-642-95335-4
11. Szabo 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
12. 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)
13. Belobrov P.K. On the Chebyshev Center of a Set. Russian Mathematics (Izvestiya VUZ. Matematika), 1964, no. 1 (38), pp. 3-9. (in Russian)
14. Toth L.F. Lagerungen in der Ebene, auf der Kugel und im Raum. Berlin, Springer, 1957.
15. Graham R.L., Lubachevsky B.D., Nurmela K.J., Ostergard 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
16. 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.
17. Markot 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
18. 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
19. Chen K., Giblin P. J., Irving A. Mathematical Explorations with MATLAB. N.Y., Cambridge University Press, 1999. DOI: 10.1017/CBO9780511624117
20. Erich's Packing Center. Available at: www2.stetson.edu (accessed May 10, 2017).