Диаграмма Вороного

---

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

Названа в честь Георгия Феодосьевича Вороного, который изучил общий n-мерный случай в 1908 году^[2]. Также известна как: мозаика Вороного, разбиение Вороного, разбиение Дирихле.

Впервые применение подобных конструкций приписывают Декарту в 1644 году.Дирихле использовал двумерные и трёхмерные диаграммы Вороного в своём труде о квадратичных формах в 1850 году.

Имеет тесную связь и взаимно-однозначное соответствие с триангуляцией Делоне. А именно, если соединить рёбрами точки, области Вороного которых граничат друг с другом, полученный граф будет являться триангуляцией Делоне.

Рассмотрим серединный перпендикуляр отрезка, соединяющего некоторую пару точек ${\displaystyle p}$ и ${\displaystyle q}$.

Этот перпендикуляр разбивает плоскость на две полуплоскости ${\displaystyle H_{pq}}$ и ${\displaystyle H_{qp}}$, причём область Вороного точки p целиком содержится в одной из них, а область точки ${\displaystyle q}$ — в другой. Область Вороного ${\displaystyle V_{p}}$ точки ${\displaystyle p}$ совпадает с пересечением всех таких полуплоскостей ${\displaystyle H_{pq}}$:

---