Open AccessAn algorithm of packing congruent circles in a multiply connected set with non-Euclidean metrics
Author(s) -
А. Л. Казаков,
A. A. Lempert,
Г.Л. Нгуен
Publication year - 2016
Publication title -
vyčislitelʹnye metody i programmirovanie
Language(s) - English
Resource type - Journals
eISSN - 1726-3522
pISSN - 0507-5386
DOI - 10.26089/nummet.v17r216
Subject(s) - container (type theory) , euclidean geometry , set (abstract data type) , euclidean distance , packing problems , metric (unit) , euclidean space , bounded function , euclidean distance matrix , space (punctuation) , algorithm , mathematics , computer science , metric space , mathematical optimization , combinatorics , discrete mathematics , geometry , engineering , mathematical analysis , programming language , mechanical engineering , operations management , operating system
Рассматривается задача об упаковке конгруэнтных кругов в ограниченное множество (контейнер) в двумерном метрическом пространстве: требуется найти такое расположение кругов в контейнере, при котором они заполнят как можно большую долю последнего. В случае, когда пространство является евклидовым, эта задачадостаточно хорошо изучена, однако существует ряд прикладных задач, в частности в области инфраструктурной логистики, которые приводят нас к необходимости использовать специальные неевклидовые метрики. Исследованию таких задач и посвящена данная работа, причем рассматриваются как односвязные, так и многосвязные контейнеры. Разработан и программно реализован алгоритм численного решения указанной задачи, основанный на оптико-геометрическом подходе. Приведены результаты вычислительного эксперимента. The problem of optimal packing of congruent circles in a bounded set (a container) in a two-dimensional metric space is considered. It is required to find an arrangement of circles in the container such that these circles occupy the largest area of the container as possible. In the case when the space is Euclidean, this problem is well known, but the case of non-Euclidean metrics is studied much worse. However, there are some applied problems leading us to the use of special non-Euclidean metrics. For example, such a situation appears in the infrastructure logistics. Here we consider the optimal packing problem in the case when the container is simply or multiply connected. A special algorithm based on the optical-geometric approach is proposed and implemented. The results of numerical experiments are discussed.