Всем привет! Недавно я захотел сдать задачу 102482G - Panda Preserve, и не смог найти нигде простой реализации построения диаграммы Вороного за $$$O(n^2)$$$.

В этом блоге я хочу рассказать о том что такое триангуляция Делоне, диаграмма Вороного, как они связаны и как их можно построить не используя сложны структур данных

Начнём с нескольких определений и фактов:

Триангуляция — это разбиение некоторого множества точек S на треугольники, при этом внутренние области треугольников не пересекаются.

Триангуляция Делоне — это такое разбиение некоторого множества точек S на треугольники, что внутри окружности каждого треугольника не находится никаких точек из множества.

Диаграмма Вороного — такое разбиение плоскости, при котором каждая область этого разбиения образует множество точек, более близких к одному из элементов множества S, чем к любому другому элементу множества.

Диаграмма Вороного и триангуляция Делоне являются двойственными графами

Свойства триангуляции Делоне

Триангуляция Делоне максимизирует минимальный угол среди всех углов всех построенных треугольников.

Триангуляция Делоне максимизирует сумму радиусов вписанных окружностей.

Триангуляция Делоне обладает минимальной суммой радиусов окружностей, описанных около треугольников, среди всех возможных триангуляций.