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

В математике диаграмма Вороного — это разбиение плоскости на области , близкие к каждому из заданного набора объектов. В простейшем случае эти объекты представляют собой просто конечное число точек на плоскости (называемых начальными точками, узлами или генераторами). Для каждого семени существует соответствующая область , называемая ячейкой Вороного , состоящая из всех точек плоскости, расположенных ближе к этому семени, чем к любой другой. Диаграмма Вороного множества точек двойственна своей триангуляции Делоне .

Диаграмма Вороного названа в честь Георгия Вороного , а также называется мозаикой Вороного , разложением Вороного , разбиением Вороного или мозаикой Дирихле (в честь Питера Густава Лежена Дирихле ). Ячейки Вороного также известны как полигоны Тиссена . ^{[1] [2] [3]} Диаграммы Вороного имеют практическое и теоретическое применение во многих областях, в основном в науке и технике , а также в изобразительном искусстве . ^{[4] [5]}

В простейшем случае, показанном на первом рисунке, нам задано конечное множество точек { _p1 , ... , pn _} на евклидовой плоскости . В этом случае каждый узел _pk является просто точкой, а соответствующая ему ячейка Вороного Rk _{состоит} из каждой точки на евклидовой плоскости, расстояние которой до pk _меньше или равно ее расстоянию до любого _{другого} pk . Каждая такая ячейка получается из пересечения полупространств и, следовательно, является (выпуклым) многогранником . ^[6] Отрезки линийдиаграммы Вороного — это все точки плоскости, равноудаленные от двух ближайших узлов. Вершины Вороного ( узлы ) — это точки, равноудаленные от трех (или более) узлов.

Позвольте быть метрическим пространством с функцией расстояния . Позвольте быть набором индексов и пусть быть кортежем (упорядоченным набором) непустых подмножеств (сайтов) в пространстве . Ячейка Вороного, или область Вороного , связанная с сайтом , представляет собой множество всех точек , расстояние до которых до не больше, чем их расстояние до других сайтов , где любой индекс, отличный от . Другими словами, если обозначает расстояние между точкой и подмножеством , то${\ стиль текста Х}$${\ стиль текста д}$${\ стиль текста К}$${\ textstyle (P_ {k}) _ {k \ in K}}$${\ стиль текста Х}$${\ textstyle R_ {к}}$${\ textstyle P_ {к}}$${\ стиль текста Х}$${\ textstyle P_ {к}}$${\ textstyle P_ {j}}$${\ стиль текста j}$${\ стиль текста к}$${\ textstyle d (x, \, A) = \ inf \ {d (x, \, a) \ mid a \ in A \}}$${\ стиль текста х}$${\ стиль текста А}$

20 точек и их ячейки Вороного (увеличенная версия ниже )

Диаграммы Вороного из 20 точек по двум разным метрикам

Манхэттенское расстояние

Это фрагмент диаграммы Вороного случайного набора точек в трехмерном поле. Как правило, поперечное сечение трехмерной мозаики Вороного не является само по себе двумерной мозаикой Вороного. (Все клетки представляют собой выпуклые многогранники .)

Приближенная диаграмма Вороного множества точек. Обратите внимание на смешанные цвета на нечеткой границе ячеек Вороного.

Мозаика Вороного возникает за счет радиального роста семян наружу.