Скелетизация многосвязной многоугольной фигуры на основе дерева смежности ее границы

Рассматривается задача построения непрерывного скелета многоугольной фигуры – замкнутой области, граница которой состоит из конечного числа простых непересекающихся многоугольников. Предлагается алгоритм вычисления скелета за время $O(n\log n)$ в худшем случае, где $n$ – общее число вершин фигуры. Отличительной особенностью алгоритма является построение двойственного к диаграмме Вороного графа смежности сайтов, образующих границу фигуры. В основе решения лежит построение дерева смежности всех многоугольников методом плоского заметания. При этом сайты и многоугольники считаются смежными, если они имеют общую касательную пустую окружность. Предложенный подход позволяет обобщить известный алгоритм Ли, используемый для построения скелета простого многоугольника, на случай многосвязной многоугольной фигуры.