Всем привет! Недавно я захотел сдать задачу 102482G - Panda Preserve, и не смог найти нигде простую реализацию построения триангуляции Делоне.
В этом блоге я хочу рассказать о том, что такое триангуляция Делоне, диаграмма Вороного, как они связаны и как их можно построить, не используя сложные структуры данных.
Начнём с нескольких определений и фактов:
Триангуляция — это разбиение некоторого множества точек S на треугольники, при этом внутренние области треугольников не пересекаются.
Триангуляция Делоне — это такое разбиение некоторого множества точек S на треугольники, что внутри окружности каждого треугольника не находится никаких точек из множества.
Диаграмма Вороного — такое разбиение плоскости, при котором каждая область этого разбиения образует множество точек, более близких к одному из элементов множества S, чем к любому другому элементу множества.
Диаграмма Вороного и триангуляция Делоне являются двойственными графами
Алгоритм построения триангуляции Делоне за $$$O(n^2)$$$
Прежде всего, стоит сказать, что триангуляция Делоне может быть построена значительно быстрее чем за $$$O(n^2)$$$. Подробнее об этом можно прочитать тут. Однако алгоритм фортуна, приведённый тут, слишком сложный для понимания, и написать его за время контеста крайне тяжело.
Реализация за $$$O(n^2)$$$ довольно простая в плане идеи и состоит из 2 шагов.
Шаг 1
Построим произвольную триангуляцию заданного множества точек. Это построение похоже на построение выпуклой оболочки. Среди всех точек множества найдём точку с наименьшей x-координатой, а если таких несколько, то с наименьшей y-координатой. Пусть это будет какая-то точка P. Сдвинем все координаты так, чтобы точка p оказалась в начале координат. Вычисляем полярные углы всех точек относительно точки p для сортировки вокруг нее.
Будем строить триангуляцию в 2 этапа:
На первом этапе соединим все точки с точкой p и соседние точки между собой. Если бы гарантировалось, что исходный набор точек образуют выпуклый многоугольник, то этого было бы уже достаточно, однако это не гарантируется.
На втором этапе будем действовать аналогично алгоритму Грэхема для построения выпуклой оболочки. Каждый раз при добавлении новой точки, необходимо проверить не нарушается ли условие выпуклости. Если нарушается, то мы нашли "впадину", которую нужно заполнить.
В этом примере, при попытке добавить вершину 3 в выпуклую оболочку, обнаружилось, что условие выпуклости нарушается, и треугольник 123 надо добавить в триангуляцию
Шаг 2
У нас уже есть какая-то триангуляция набора точек, однако она пока что не удовлетворяет критериям триангуляции Делоне. Будем итеративно улучшать нашу триангуляцию. На каждом шаге будем искать четырехугольник ABCD такой, что в нем есть ребро AC и треугольники ABC и ACD не удовлетворяют критерию Делоне. Операцией flip будем называть удаления ребра AC и добавления ребра BD. Например, если изначально у нас были треугольники ABC и ACD, то после применения операции будут треугольники ABD и BCD. Можно доказать, что если исходное разбиение не удовлетворяет критерию Делоне, то flip решает эту проблему. Однако для краткости я не буду приводить это доказательство здесь. Этот процесс повторяется до тех пор, пока все ребра не будут удовлетворять критерию Делоне
Пример операции flip
Связь с диаграммой Вороного
На самом деле, имея триангуляцию Делоне, построить диаграмму Вороного очень легко. Достаточно для каждого треугольника найти центр описанной окружности, соединить между собой центры описанных окружностей соседних треугольников и провести лучи в бесконечность у тех треугольников, для которых нет соседей.
Связь диаграммы Вороного и триангуляции Делоне (чёрные линии — триангуляция Делоне, красные — диаграмма Вороного).
Обобщение Итеративный flip-алгоритм работает за $$$O(n^2)$$$ в худшем случае, так как в худшем случае требуется провести до (O(n)) операций флипа на каждый из $$$O(n)$$$ ребер, которые могут быть подвержены операции flip. Как уже говорилось ранее, существуют значительно более быстрые и точные способы найти триангуляцию Делоне, однако этот алгоритм более прост для понимания и его вполне можно написать за 30-40 минут.
Здесь я привожу реализацию алгоритма, однако, хотя этот код и прошёл все тесты задачи 102482G - Panda Preserve, я всё же на месте читателя написал бы его сам.
Инструмент, где можно посмотреть разные триангуляции, которые выдает этот код
