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

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

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

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

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

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

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