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

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

Точки, расположенные к опорной точке $p$ не дальше, чем к другой точке $q$, образуют полуплоскость, ограниченную серединным перпендикуляром к $pq$. Область $p$ — пересечение таких полуплоскостей, по одной для каждой другой опорной точки, поэтому она выпукла. Только некоторые серединные перпендикуляры становятся рёбрами. Опорные точки, области которых имеют общее ребро с областью $p$, — её соседи; остальные полуплоскости уже содержат всю область. Рамка лишь ограничивает окно. Область уходит в бесконечность тогда и только тогда, когда её опорная точка лежит на границе выпуклой оболочки всех опорных точек.

В вершине, где сходятся три или больше областей, расстояния до их опорных точек одинаковы. Поэтому вершина — центр окружности, проходящей через эти точки. Внутри неё нет опорных точек: такая точка была бы ближе к вершине, и вершина принадлежала бы её области. Обычно в вершине сходятся ровно три области. Четыре сходятся, когда ровно четыре опорные точки лежат на одной пустой окружности, как в квадратной сетке. У случайно рассеянных точек такое почти никогда не встречается.

Рост увеличивает круг вокруг каждой опорной точки с одинаковой скоростью. Каждое место сначала достигается из ближайшей опорной точки, поэтому фронты встречаются точно вдоль рёбер. Маленький вид показывает тот же рост сбоку. Над каждым местом высота равна расстоянию до ближайшей опорной точки: это наименьшая высота конусов $z = |x - s|$, стоящих на опорных точках. Гребни — рёбра, а рост — подъём воды. Последним затапливается самый высокий участок рельефа внутри рамки: центр наибольшего пустого круга с центром в рамке.

Триангуляция соединяет две опорные точки, если их области имеют общее ребро, и добавляет пунктирные диагонали, когда четыре или больше точек лежат на одной пустой окружности, как в квадратной сетке. Если не все точки лежат на одной прямой, получается триангуляция Делоне. Описанная окружность каждого треугольника — пустая окружность вокруг вершины диаграммы.

Выровнять переносит каждую опорную точку в центр тяжести её области, обрезанной рамкой, и заново строит области, шаг за шагом. Это алгоритм Ллойда. Маленький график показывает средний квадрат расстояния от точки внутри рамки до ближайшей опорной точки, делённый на площадь рамки в расчёте на одну опорную точку. Ни один шаг не может увеличить это значение. При фиксированных опорных точках его минимизируют области ближайшей точки; при фиксированных областях — центры тяжести. Линия сот — нижняя граница: значение для одинаковых правильных шестиугольников с опорными точками в центрах. Из рассеянного набора процесс приходит в одно из близких устойчивых состояний, а не к идеальным сотам. Обычно рядом остаются пятиугольники и семиугольники, как дислокации в кристалле.

Диаграмма названа в честь Георгия Вороного, который в 1908 году изучал такие разбиения в любой размерности, а триангуляция — в честь Бориса Делоне, описавшего её в 1934 году.