RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



УБС:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


УБС, 2019, выпуск 81, страницы 6–25 (Mi ubs1015)  

Системный анализ

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

А. Л. Казаковa, А. А. Лемпертa, К. М. Леb

a Институт динамики систем и теории управления им. В.М. Матросова СО РАН, Иркутск
b Иркутский национальный исследовательский технический университет, Иркутск

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

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

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 18-07-00604
Работа выполнена при поддержке Российского фонда фундаментальных исследований (проект № 18-07-00604).


DOI: https://doi.org/10.25728/ubs.2019.81.1

Полный текст: PDF файл (2179 kB)
Список литературы: PDF файл   HTML файл

Тип публикации: Статья
УДК: 514.174.2
ББК: 22.19
Поступила в редакцию: 19 июля 2019 г.
Опубликована: 30 сентября 2019 г.

Образец цитирования: А. Л. Казаков, А. А. Лемперт, К. М. Ле, “О задачах построения многократных покрытий и упаковок в двумерном неевклидовом пространстве”, УБС, 81 (2019), 6–25

Цитирование в формате AMSBIB
\RBibitem{KazLemLe19}
\by А.~Л.~Казаков, А.~А.~Лемперт, К.~М.~Ле
\paper О задачах построения многократных покрытий и упаковок в двумерном неевклидовом пространстве
\jour УБС
\yr 2019
\vol 81
\pages 6--25
\mathnet{http://mi.mathnet.ru/ubs1015}
\crossref{https://doi.org/10.25728/ubs.2019.81.1}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/ubs1015
  • http://mi.mathnet.ru/rus/ubs/v81/p6

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Управление большими системами
    Просмотров:
    Эта страница:36
    Полный текст:17
    Литература:2
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020