Страница публикации

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

Тип публикации: Статья в журнале

Тип материала: Текст

Авторы: Казаков А.Л., Лебедев П.Д.

Журнал: Вычисл. методы и программирование

Язык публикации: russian

Том: 16

Номера страниц: 307-317

Количество страниц: 11

Номер: 2

Год публикации: 2015

Отчетный год: 2015

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

Индексируется WOS: Нет

Индексируется Scopus: Нет

Индексируется УБС: Нет

Индексируется РИНЦ: Да

Индексируется ВАК: Нет

Индексируется CORE: Нет