Алгоритмы построения оптимальных упаковок в эллипсы

В задачах теории управления часто требуется проводить аппроксимацию множеств наборами из конгруэнтных элементов. Одним из вариантов такой аппроксимации служит упаковка в фигуры на плоскости набора кругов равного радиуса. В статье рассмотрены два варианта задачи о построении оптимальной упаковки в эллипсы различной формы: в первом фиксировано число элементов и требуется максимизировать их радиус, во втором фиксирован радиус кругов и требуется максимизировать их число. В первом варианте применяются итерационные методы, имитирующие отталкивание центров кругов друг от друга и от границы множества. В них используются конструкции чебышевского центра, ортогональных проекций и отталкивания точек. Во втором - рассматриваются упаковки с гексагональной решеткой, которые близки к оптимальным. Реализован программный комплекс построения упаковок для эллипсов с различным соотношением осей.

Ключевые слова

упаковка; хаусдорфово отклонение; максимизация; чебышевский центр; производная по направлению.

Литература

1. Красовский, Н.Н. Позиционные дифференциальные игры / Н.Н. Красовский, А.И. Субботин. - М.: Наука, 1974. - 456 с.
2. Ушаков, В.Н. Конструирование решений в задаче о сближении стационарной управляемой системы / В.Н. Ушаков, Н.Г. Лавров, А.В. Ушаков // Труды Института математики и механики УрО РАН. - 2014. - Т. 20, № 4. - С. 277-286.
3. Kurzhanski, A.B. Ellipsoidal Calculus for Estimation and Control / A.B. Kurzhanski, I. Valyi. - Basel: Birkhauser, 1997.
4. Слоэн, Дж. Упаковка шаров / Дж. Слоэн // Scientific American. - 1984. - № 3. - С. 72-82.
5. Ушаков, В.Н. Оптимизация хаусдорфова расстояния между множествами в евклидовом пространстве / В.Н. Ушаков, А.С. Лахтин, П.Д. Лебедев // Труды Института математики и механики УрО РАН. - 2014. - Т. 20, № 3. - C. 291-308.
6. Казаков, А.Л. Алгоритмы построения оптимальных упаковок для компактных множеств на плоскости / А.Л. Казаков, П.Д. Лебедев // Вычислительные методы и программирование. - 2015. - Т. 16, № 3. - С. 307-317.
7. Демьянов, В.Ф. Недифференцируемая оптимизация / В.Ф. Демьянов, Л.В. Васильев. - М.: Наука, 1981. - 384 с.
8. Демьянов, В.Ф. Основы негладкого анализа и квазидифференциальное исчисление / В.Ф. Демьянов, А.М. Рубинов. - М.: Наука, 1990. - 432 с.
9. Сухарев, А.Г. Курс методов оптимизации / А.Г. Сухарев, А.В. Тимохов, В.В. Федоров. - М.: Наука, 1986. - 326 с.
10. Лейхтвейс К. Выпуклые множества / К. Лейхтвейс. - М.: Наука, 1985. - 335 с.
11. Szabo, P.G. Packing up to 200 equal circles in a square / P.G. Szab'o, E. Specht // Models and Algorithms for Global Optimization. - 2007. - P. 141-156.
12. Гаркави, А.Л. О чебышевском центре и выпуклой оболочке множества / А.Л. Гаркави // Успехи математических наук. - 1964. - Т. 19, № 6. - С. 139-145.
13. Белобров, П.К. К вопросу о чебышевском центре множества / П.К. Белобров // Известия высших учебных заведений. Математика. - 1964. - № 1. - C. 3-9.
14. Тот, Л.Ф. Расположения на плоскости, на сфере и в пространстве / Л.Ф. Тот. - М.: Государственное издательство физико-математической литературы, 1958. - 365 c.
15. Graham, R.L. Dense Packings of Congruent Circles in a Circle / R.L. Graham, B.D. Lubachevsky, K.J. Nurmela, P.R.J. Ostergard // Discrete Mathematics. - 1998. - № 181. - P. 139-154.
16. Lubachevsky, B.D. Curved Hexagonal Packings of Equal Disks in a Circle / B.D. Lubachevsky, R.L. Graham // Discrete & Computational Geometry. - 1997. - V. 18, № 2. - P. 179-194.
17. Markot, M.Cs. A New Verified Optimization Technique for the "Packing Circles in a Unit Square" Problems / M.Cs. Markot, T.A. Csendes // SIAM Journal on Optimization. - 2005. - V. 16, № 1. - P. 193-219.
18. Goldberg, M. Packing of 14, 16, 17 and 20 Circles in a Circle / M. Goldberg // Mathematics Magazine. - 1971. - V. 44, № 3. - P. 134-139.
19. Чен, К. MATLAB в математических исследованиях / К. Чен, П. Джиблин, А. Ирвинг. - М.: Мир, 2001.
20. Erich's Packing Center. - URL: www2.stetson.edu (дата обращения: 10.05.2017)