Алгоритмы построения оптимальных упаковок в эллипсы
Автор: Ушаков Владимимир Николаевич, Лебедев Павел Дмитриевич, Лавров Никита Георгиевич
Рубрика: Математическое моделирование
Статья в выпуске: 3 т.10, 2017 года.
Бесплатный доступ
В задачах теории управления часто требуется проводить аппроксимацию множеств наборами из конгруэнтных элементов. Одним из вариантов такой аппроксимации служит упаковка в фигуры на плоскости набора кругов равного радиуса. В статье рассмотрены два варианта задачи о построении оптимальной упаковки в эллипсы различной формы: в первом фиксировано число элементов и требуется максимизировать их радиус, во втором фиксирован радиус кругов и требуется максимизировать их число. В первом варианте применяются итерационные методы, имитирующие отталкивание центров кругов друг от друга и от границы множества. В них используются конструкции чебышевского центра, ортогональных проекций и отталкивания точек. Во втором - рассматриваются упаковки с гексагональной решеткой, которые близки к оптимальным. Реализован программный комплекс построения упаковок для эллипсов с различным соотношением осей.
Упаковка, хаусдорфово отклонение, максимизация, чебышевский центр, производная по направлению
Короткий адрес: https://sciup.org/147159444
IDR: 147159444 | УДК: 514.174.2 | DOI: 10.14529/mmp170306
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.
Список литературы Алгоритмы построения оптимальных упаковок в эллипсы
- Красовский, Н.Н. Позиционные дифференциальные игры/Н.Н. Красовский, А.И. Субботин. -М.: Наука, 1974. -456 с.
- Ушаков, В.Н. Конструирование решений в задаче о сближении стационарной управляемой системы/В.Н. Ушаков, Н.Г. Лавров, А.В. Ушаков//Труды Института математики и механики УрО РАН. -2014. -Т. 20, № 4. -С. 277-286.
- Kurzhanski, A.B. Ellipsoidal Calculus for Estimation and Control/A.B. Kurzhanski, I. Valyi. -Basel: Birkhäuser, 1997.
- Слоэн, Дж. Упаковка шаров/Дж. Слоэн//Scientific American. -1984. -№ 3. -С. 72-82.
- Ушаков, В.Н. Оптимизация хаусдорфова расстояния между множествами в евклидовом пространстве/В.Н. Ушаков, А.С. Лахтин, П.Д. Лебедев//Труды Института математики и механики УрО РАН. -2014. -Т. 20, № 3. -C. 291-308.
- Казаков, А.Л. Алгоритмы построения оптимальных упаковок для компактных множеств на плоскости/А.Л. Казаков, П.Д. Лебедев//Вычислительные методы и программирование. -2015. -Т. 16, № 3. -С. 307-317.
- Демьянов, В.Ф. Недифференцируемая оптимизация/В.Ф. Демьянов, Л.В. Васильев. -М.: Наука, 1981. -384 с.
- Демьянов, В.Ф. Основы негладкого анализа и квазидифференциальное исчисление/В.Ф. Демьянов, А.М. Рубинов. -М.: Наука, 1990. -432 с.
- Сухарев, А.Г. Курс методов оптимизации/А.Г. Сухарев, А.В. Тимохов, В.В. Федоров. -М.: Наука, 1986. -326 с.
- Лейхтвейс К. Выпуклые множества/К. Лейхтвейс. -М.: Наука, 1985. -335 с.
- Szabó, P.G. Packing up to 200 equal circles in a square/P.G. Szabó, E. Specht//Models and Algorithms for Global Optimization. -2007. -P. 141-156.
- Гаркави, А.Л. О чебышевском центре и выпуклой оболочке множества/А.Л. Гаркави//Успехи математических наук. -1964. -Т. 19, № 6. -С. 139-145.
- Белобров, П.К. К вопросу о чебышевском центре множества/П.К. Белобров//Известия высших учебных заведений. Математика. -1964. -№ 1. -C. 3-9.
- Тот, Л.Ф. Расположения на плоскости, на сфере и в пространстве/Л.Ф. Тот. -М.: Государственное издательство физико-математической литературы, 1958. -365 c.
- Graham, R.L. Dense Packings of Congruent Circles in a Circle/R.L. Graham, B.D. Lubachevsky, K.J. Nurmela, P.R.J. Östergård//Discrete Mathematics. -1998. -№ 181. -P. 139-154.
- 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.
- Markót, M.Cs. A New Verified Optimization Technique for the "Packing Circles in a Unit Square" Problems/M.Cs. Markót, T.A. Csendes//SIAM Journal on Optimization. -2005. -V. 16, № 1. -P. 193-219.
- Goldberg, M. Packing of 14, 16, 17 and 20 Circles in a Circle/M. Goldberg//Mathematics Magazine. -1971. -V. 44, № 3. -P. 134-139.
- Чен, К. MATLAB в математических исследованиях/К. Чен, П. Джиблин, А. Ирвинг. -М.: Мир, 2001.
- Erich's Packing Center. -URL: www2.stetson.edu (дата обращения: 10.05.2017)
