Open AccessAlgorithms of optimal packing construction for planar compact sets
Author(s) -
А. Л. Казаков,
П. Д. Лебедев
Publication year - 2015
Publication title -
vyčislitelʹnye metody i programmirovanie
Language(s) - English
Resource type - Journals
eISSN - 1726-3522
pISSN - 0507-5386
DOI - 10.26089/nummet.v16r230
Subject(s) - voronoi diagram , packing problems , mathematics , polygon (computer graphics) , boundary (topology) , planar , euclidean geometry , point in polygon , algorithm , set (abstract data type) , power diagram , sphere packing , euclidean distance , function (biology) , set packing , mathematical optimization , computer science , regular polygon , geometry , mathematical analysis , computer graphics (images) , programming language , telecommunications , frame (networking) , evolutionary biology , biology
Рассматривается задача об упаковке заданного числа равных кругов в компактное множество на плоскости при наибольшем возможном их радиусе. Разработан аналитический алгоритм отыскания наилучшей упаковки одного круга в многоугольник в евклидовом пространстве, основанный на максимизации функции расстояния от границы. На его основе создан алгоритм итерационного улучшения упаковки в выпуклое множество, использующий разбиение на подмножества (зоны Дирихле) с помощью диаграммы Вороного. Предложен численный алгоритм построения упаковки для случаев невыпуклого множества и неевклидовой метрики, основанный на оптико-геометрической аналогии. Проведено численное решение ряда примеров при большом количестве элементов упаковки в евклидовом пространстве и для одной специальной неевклидовой метрики. The best packing problem for a prescribed number of equal disks in a compact planar set with their minimally possible radius is considered. An analytical algorithm for constructing the one disk best packing in a polygon in Euclidean space based on the maximization of the distance function from the boundary is proposed. An iteration algorithm based on the previous one is developed using the splitting into subsets (Dirichlet zones) with the aid of the Voronoi diagram. A numerical algorithm for packing in a nonconvex set in non-Euclidian metrics based on the optical geometric analogy is also proposed. A number of examples are numerically solved with a large number of packing elements and for a special non-Euclidian metrics.