О задачах построения многократных покрытий и упаковок в двумерном неевклидовом пространстве

Автор(ы): Казаков А.Л., Лемперт А.А., Ле К.М.

Выпуск: 81

Рубрика: Системный анализ

Год: 2019

Библиография: Казаков А.Л., Лемперт А.А., Ле К.М. О задачах построения многократных покрытий и упаковок в двумерном неевклидовом пространстве // Управление большими системами. Вып. 81. М.: ИПУ РАН, 2019. С.6-25. DOI: https://doi.org/10.25728/ubs.2019.81.1

Дата опубликования: 30.09.2019

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

Аннотация: Статья посвящена изучению двух содержательных задач вычислительной геометрии: задачи построения оптимальных многократных покрытий кругами замкнутого ограниченного множества в двумерном метрическом пространстве и аналогичной задачи упаковки кругов. В обоих случаях число кругов фиксировано. В первом случае целью является минимизация, а во втором --- максимизация радиуса кругов. Рассматриваемая метрика, вообще говоря, неевклидова. Источником такой постановки является транспортная логистика, где встречаются задачи, в которых расстояние между объектами необходимо заменить минимальным временем перемещения между ними, при этом искомый оптимум в силу особенностей местности далеко не всегда достигается при движении по прямой линии. Для решения задач предложены вычислительные алгоритмы, которые основаны на применении оптико-геометрического подхода, базирующегося на принципах геометрической оптики Ферма и Гюйгенса, и методе K-средних. Ключевым этапом работы в обоих случаях является построение обобщенной диаграммы Вороного порядка k, каждая ячейка которой при фиксированном наборе из n центроидов включает в себя точки, расположенные ближе к некоторым k центроидам, чем к оставшимся n-k. При этом, в отличие от классической диаграммы Вороного, здесь ячейки могут пересекаться. Проведены вычислительные эксперименты, выполнены обсуждение и интерпретация их результатов.

Author(s): Kazakov A., Lempert A., Le Q.M.

Article title: On multiple coverings and packings problems in a two-dimensional non-euclidean space

Issue: 81

Year: 2019

Keywords: multiple packing, equal circles, non-Euclidean metric, algorithm, Voronoi -- Dirichlet diagram, Fermat and Huygens principles

Abstract: The article is devoted to the study of two significant problems of computational geometry. The first one is the multiple circle covering problem for a closed bounded set in a two-dimensional metric space, and the second one is the multiple circle packing problem. In the first case, the objective is to minimize the radius of the circles, in the second one is to maximize it. In both cases, the number of circles k is given. The considered metric is generally non-Euclidean. The source of such a statement is tasks from transport logistics, where the distance between objects is necessary to be replaced with a minimum time to travel between them. And optimum is not always achieved with straight line moving due to the terrain or urban features. We propose computational algorithms to solve these problems. They include the joint use of an optical-geometric approach based on the principles of Fermat and Huygens and the K-means method. The key step is to construct a generalized k-order Voronoi diagram. Each Voronoi cell with a fixed set of n centroids includes points, which are closer to some k centroids than to the remaining n-k . The cells can intersect each other. Computational experiments are carried out.