|
Вычислительные методы и программирование, 2015, том 16, выпуск 2, страницы 307–317
(Mi vmp542)
|
|
|
|
Эта публикация цитируется в 7 научных статьях (всего в 7 статьях)
Алгоритмы построения оптимальных упаковок для компактных множеств на плоскости
А. Л. Казаковa, П. Д. Лебедевb a Институт динамики систем и теории управления имени В.М. Матросова Сибирского отделения Российской академии наук, г. Иркутск
b Институт математики и механики им. Н. Н. Красовского Уральского отделения РАН, г. Екатеринбург
Аннотация:
Рассматривается задача об упаковке заданного числа равных кругов в компактное множество на плоскости при наибольшем возможном их радиусе. Разработан аналитический алгоритм отыскания наилучшей упаковки одного круга в многоугольник в евклидовом пространстве, основанный на максимизации функции расстояния от границы. На его основе создан алгоритм итерационного улучшения упаковки в выпуклое множество, использующий разбиение на подмножества (зоны Дирихле) с помощью диаграммы Вороного. Предложен численный алгоритм построения упаковки для случаев невыпуклого множества и неевклидовой метрики, основанный на оптико-геометрической аналогии. Проведено численное решение ряда примеров при большом количестве элементов упаковки в евклидовом пространстве и для одной специальной неевклидовой метрики.
Ключевые слова:
упаковка кругов, зона Дирихле, диаграмма Вороного, оптико-геометрический метод, вычислительный алгоритм, программный комплекс.
Поступила в редакцию: 27.03.2015
Образец цитирования:
А. Л. Казаков, П. Д. Лебедев, “Алгоритмы построения оптимальных упаковок для компактных множеств на плоскости”, Выч. мет. программирование, 16:2 (2015), 307–317
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/vmp542 https://www.mathnet.ru/rus/vmp/v16/i2/p307
|
Статистика просмотров: |
Страница аннотации: | 363 | PDF полного текста: | 317 |
|