Автор:  Казаков А.Л., Лемперт А.А., Ле К.М.
Название:  О задачах построения многократных покрытий и упаковок в двумерном неевклидовом пространстве
Выпуск:  81
Рубрика:  Системный анализ
Год:  2019
Библиография:  Казаков А.Л., Лемперт А.А., Ле К.М. О задачах построения многократных покрытий и упаковок в двумерном неевклидовом пространстве // Управление большими системами. Вып. 81. М.: ИПУ РАН, 2019. С.6-25. DOI: https://doi.org/10.25728/ubs.2019.81.1
Ключевые слова:  многократное покрытие множества, многократная упаковка кругов, неевклидова метрика, вычислительный алгоритм, оптико-геометрический подход, диаграмма Вороного, численный эксперимент
Ключевые слова (англ.):  multiple packing, equal circles, non-Euclidean metric, algorithm, Voronoi -- Dirichlet diagram, Fermat and Huygens principles
Аннотация:  Статья посвящена изучению двух содержательных задач вычислительной геометрии: задачи построения оптимальных многократных покрытий кругами замкнутого ограниченного множества в двумерном метрическом пространстве и аналогичной задачи упаковки кругов. В обоих случаях число кругов фиксировано. В первом случае целью является минимизация, а во втором --- максимизация радиуса кругов. Рассматриваемая метрика, вообще говоря, неевклидова. Источником такой постановки является транспортная логистика, где встречаются задачи, в которых расстояние между объектами необходимо заменить минимальным временем перемещения между ними, при этом искомый оптимум в силу особенностей местности далеко не всегда достигается при движении по прямой линии. Для решения задач предложены вычислительные алгоритмы, которые основаны на применении оптико-геометрического подхода, базирующегося на принципах геометрической оптики Ферма и Гюйгенса, и методе K-средних. Ключевым этапом работы в обоих случаях является построение обобщенной диаграммы Вороного порядка k, каждая ячейка которой при фиксированном наборе из n центроидов включает в себя точки, расположенные ближе к некоторым k центроидам, чем к оставшимся n-k. При этом, в отличие от классической диаграммы Вороного, здесь ячейки могут пересекаться. Проведены вычислительные эксперименты, выполнены обсуждение и интерпретация их результатов.
Аннотация (англ.):  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.

В формате PDF
Обсудить статью в Интернет-конференции по проблемам управления

Просмотров: 2155, загрузок: 685, за месяц: 21.

Назад