Алгоритмы построения оптимальных упаковок для компактных множеств на плоскости
Казаков А.Л., Лебедев П.Д.

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

Ключевые слова: упаковка кругов, зона Дирихле, диаграмма Вороного, оптико-геометрический метод, вычислительный алгоритм, программный комплекс.

Название статьи, аннотация и ключевые слова на английском языке

  • Казаков А.Л. – Институт динамики систем и теории управления им. В.М. Матросова СО РАН, ул. Лермонтова, 134, 664033, г. Иркутск; зав. лабораторией, e-mail: kazakov@icc.ru
  • Лебедев П.Д. – Институт математики и механики им. Н.Н. Красовского УрО РАН, ул. С. Ковалевской, 16, 620990, г. Екатеринбург; науч. сотр., e-mail: pleb@yandex.ru