Алгоритмы построения оптимальных упаковок в эллипсы
DOI:
https://doi.org/10.14529/mmp170306Ключевые слова:
упаковка, хаусдорфово отклонение, максимизация, чебышевский центр, производная по направлениюАннотация
В задачах теории управления часто требуется проводить аппроксимацию множеств наборами из конгруэнтных элементов. Одним из вариантов такой аппроксимации служит упаковка в фигуры на плоскости набора кругов равного радиуса. В статье рассмотрены два варианта задачи о построении оптимальной упаковки в эллипсы различной формы: в первом фиксировано число элементов и требуется максимизировать их радиус, во втором фиксирован радиус кругов и требуется максимизировать их число. В первом варианте применяются итерационные методы, имитирующие отталкивание центров кругов друг от друга и от границы множества. В них используются конструкции чебышевского центра, ортогональных проекций и отталкивания точек. Во втором - рассматриваются упаковки с гексагональной решеткой, которые близки к оптимальным. Реализован программный комплекс построения упаковок для эллипсов с различным соотношением осей.Библиографические ссылки
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).
