Эта публикация цитируется в
2 статьях
Итерационные методы построения упаковок из кругов различного диаметра на плоскости
П. Д. Лебедевa,
А. Л. Казаковb a Институт математики и механики им. Н. Н. Красовского Уральского отделения РАН, г. Екатеринбург
b Институт динамики систем и теории управления имени В.М. Матросова Сибирского отделения Российской академии наук, г. Иркутск
Аннотация:
Рассматривается задача о построении оптимальной упаковки из фиксированного числа
$n>1$ кругов в общем случае различного радиуса в плоское компактное множество
$M$. Считается, что для каждого элемента упаковки задано положительное число такое, что радиус круга равен его произведению на общий для всей упаковки параметр
$r$. Критерием оптимальности выбран максимум
$r$, что приводит в том числе и к увеличению плотностиупаковки - отношения ее площади к площади фигуры
$M$. Основу метода решения задачи составляет итерационное изменение координат центров элементов упаковки
$S_n$, дающее возможность увеличивать радиусы кругов. Разработанные вычислительные процедуры реализуют имитацию отталкивания центра каждого элемента упаковки от близко лежащих других центров и от границы множества
$M$. Исследованы дифференциальные свойства функции двух переменных
$(x,y)$, значение которой равно максимальному радиусу круга упаковки, располагающегося с центром в точке
$(x,y)$. При это координаты центров остальных элементов упаковки считаются фиксированными. При программной реализации используется конструкция чебышевского центра компактного множества. Создан программный комплекс, с его помощью рассмотрен ряд примеров для множеств
$M$ различной геометрии. Выполнена визуализация полученных результатов.
Ключевые слова:
задача об упаковке кругов, оптимизация, чебышевский центр, супердифференциал, итерационный алгоритм.
УДК:
514.174.2
MSC: 05B40,
28A78,
52C15,
52C26 Поступила в редакцию: 15.03.2018
DOI:
10.21538/0134-4889-2018-24-2-141-151