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

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