|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Системный анализ
О задачах построения многократных покрытий и упаковок в двумерном неевклидовом пространстве
А. Л. Казаковa, А. А. Лемпертa, К. М. Леb a Институт динамики систем и теории управления им. В.М. Матросова СО РАН, Иркутск
b Иркутский национальный исследовательский технический университет, Иркутск
Аннотация:
Статья посвящена изучению двух содержательных задач вычислительной геометрии: задачи построения оптимальных многократных покрытий кругами замкнутого ограниченного множества в двумерном метрическом пространстве и аналогичной задачи упаковки кругов. В обоих случаях число кругов фиксировано. В первом случае целью является минимизация, а во втором — максимизация радиуса кругов. Рассматриваемая метрика, вообще говоря, неевклидова. Источником такой постановки является транспортная логистика, где встречаются задачи, в которых расстояние между объектами необходимо заменить минимальным временем перемещения между ними, при этом искомый оптимум в силу особенностей местности далеко не всегда достигается при движении по прямой линии. Для решения задач предложены вычислительные алгоритмы, которые основаны на применении оптико-геометрического подхода, базирующегося на принципах геометрической оптики Ферма и Гюйгенса, и методе $K$-средних. Ключевым этапом работы в обоих случаях является построение обобщенной диаграммы Вороного порядка $k$, каждая ячейка которой при фиксированном наборе из $n$ центроидов включает в себя точки, расположенные ближе к некоторым $k$ центроидам, чем к оставшимся $n-k$. При этом, в отличие от классической диаграммы Вороного, здесь ячейки могут пересекаться. Проведены вычислительные эксперименты, выполнены обсуждение и интерпретация их результатов.
Ключевые слова:
многократное покрытие множества, многократная упаковка кругов, неевклидова метрика, вычислительный алгоритм, оптико-геометрический подход, диаграмма Вороного, численный эксперимент.
Поступила в редакцию: 19 июля 2019 г. Опубликована: 30 сентября 2019 г.
Образец цитирования:
А. Л. Казаков, А. А. Лемперт, К. М. Ле, “О задачах построения многократных покрытий и упаковок в двумерном неевклидовом пространстве”, УБС, 81 (2019), 6–25
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/ubs1015 https://www.mathnet.ru/rus/ubs/v81/p6
|
Статистика просмотров: |
Страница аннотации: | 236 | PDF полного текста: | 83 | Список литературы: | 34 |
|