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

1908 год. Метеоролог Тиссен разбивает карту осадков на зоны ближайших станций. 2020 год. Uber назначает ближайшего водителя. Google Maps строит районы доставки. Та же геометрия - диаграмма Вороного. Fortune's algorithm строит её за $O(N \log N)$ для $N$ точек. Naïve подход (для каждой точки найти ближайшую) требует $O(N^2)$. При $N = 10^6$ разница в 50 000 раз. Граница 1-NN классификатора - точно диаграмма Вороного. k-means сходится к ней же. Одна геометрическая структура за треть всего machine learning.

• Uber/Lyft: зоны назначения водителей через взвешенную диаграмму Вороного по времени поездки, не евклидову расстоянию
• k-means кластеризация: Lloyd's algorithm сходится к центроидной диаграмме Вороного - явная геометрическая интерпретация
• Game engines: NavMesh и Voronoi fracture - разбиение меша на обломки при взрыве через диаграмму Вороного
• Медицинская гистология: зоны влияния клеток в срезах ткани, анализ плотности и паттернов расположения

Тиссен, Вороной, Фортуна

Георгий Вороной опубликовал математическое определение разбиения в 1908 году. В том же году метеоролог Альберт Тиссен независимо применил ту же идею к осадкам - в метеорологии структуру до сих пор называют полигонами Тиссена. Физик Дирихле изучал похожие разбиения ещё в 1850-х - иногда говорят 'разбиение Дирихле'. Эффективный алгоритм построения появился только в 1987 году: Стивен Фортуна опубликовал sweep line подход, снизив сложность с $O(N^2)$ до $O(N \log N)$ worst-case. До этого 80 лет структура была известна, но строилась медленно.

Ячейка Вороного: зона ближайшей точки

1908 год. Метеоролог Тиссен разбивает карту осадков на зоны: каждая точка плоскости принадлежит ближайшей измерительной станции. Это и есть диаграмма Вороного. Формально: для множества точек $P = \{p_1, ..., p_n\}$ ячейка $V(p_i) = \{x \in \mathbb{R}^2 : d(x, p_i) \leq d(x, p_j) \; \forall j \neq i\}$ - пересечение $n-1$ полуплоскостей. Результат: $n$ выпуклых многоугольников, покрывающих всю плоскость без перекрытий.

Каждая ячейка $V(p_i)$ - выпуклый многоугольник (пересечение конечного числа полуплоскостей). Граничные точки на выпуклой оболочке дают **неограниченные** ячейки. Вершина диаграммы Вороного - точка, равноудалённая от трёх и более сайтов. Рёбра - перпендикулярные биссектрисы пар сайтов.

**ML-связь**: граница решения 1-NN классификатора - точно диаграмма Вороного. Каждая ячейка $V(p_i)$ содержит все точки запроса, для которых ближайшим обучающим примером является $p_i$. Decision boundary 1-NN в пространстве признаков геометрически эквивалентен диаграмме Вороного обучающей выборки.

Хранение диаграммы: DCEL (Doubly Connected Edge List) - структура half-edge. Каждое ребро хранится как пара направленных half-edge, каждый содержит указатели на: origin vertex, twin half-edge, next half-edge в грани, инцидентную грань. Позволяет обходить ячейку за $O(\deg)$ без глобального поиска.

Алгоритм Фортуна: sweep line за O(N log N)

1987 год. Стивен Фортуна публикует sweep line алгоритм для диаграммы Вороного. Naïve подход - для каждой из $N$ точек найти ближайшую - требует $O(N^2)$. Fortune: $O(N \log N)$. При $N = 10^6$ это разница в 50 000 раз. Идея: метла движется сверху вниз. Перед метлой - необработанные сайты. За метлой - уже построенная часть диаграммы. Между ними - **beach line**: огибающая парабол, каждая из которых порождена одним сайтом.

Сложность Fortune: $O(N \log N)$ worst-case (priority queue + balanced BST для beach line). Пространство: $O(N)$. Circle event - потенциально ложное (false alarm): если средний сайт из тройки удаляется с beach line раньше, circle event отменяется. Fortune обрабатывает это lazy deletion из priority queue.

Двойственность: Вороного и Делоне - одна структура

Парадокс: алгоритм Фортуна строит диаграмму Вороного, а вершины этой диаграммы - центры описанных кругов треугольников Делоне. Два алгоритма, одна структура данных. Двойственность: соединить два сайта ребром Делоне, если их ячейки Вороного имеют общее ребро. Ребро Делоне перпендикулярно ребру Вороного. Критерий Делоне (пустой описанный круг) и вершина Вороного (равноудалённая от трёх сайтов) - одно и то же событие.

**Применения двойственности**: flip алгоритм из cgeom-04 работает через диаграмму Вороного. Mesh generation для FEM: Ruppert's algorithm добавляет точки Вороного (circumcenters) для улучшения качества mesh. Terrain rendering в игровых движках: Делоне триангуляция heightmap, Вороного для Voronoi fracture (разбиение меша на обломки при взрыве).

В 3D двойственность сохраняется: Делоне тетраэдрализация двойственна 3D диаграмме Вороного. Используется в FEM (Ansys, Abaqus), молекулярной динамике (Вороного разбиение кристаллической решётки) и reconstruction из point cloud (Poisson surface reconstruction).

Применения: от k-means до робототехники

Диаграмма Вороного для $L_\infty$ нормы - квадратная, не округлая. Uber использует не евклидово расстояние, а время поездки. Геометрия разбиения зависит от метрики. При этом структура та же: зона ближайшего сайта по выбранной метрике. Для facility location задача оптимальная: разместить $k$ объектов так, чтобы минимизировать средний путь - это Lloyd's algorithm, известный как k-means кластеризация.

**Lloyd's algorithm = k-means = центроидная диаграмма Вороного**. Итерация: 1) построить диаграмму Вороного для текущих центроидов; 2) переместить каждый центроид в центр масс своей ячейки. Повторять до сходимости. k-means сходится к **центроидной диаграмме Вороного** - конфигурации, где каждый сайт совпадает с центром своей ячейки.

**Nearest neighbor search**: для $k$-NN задачи диаграмма Вороного даёт 1-NN за $O(\log N)$ (point location в диаграмме). Для $k > 1$: k-order Вороного диаграмма или k-d tree. На практике FLANN (Approximate Nearest Neighbors) + k-d tree быстрее для высоких размерностей из-за curse of dimensionality.

Ключевые идеи

• **Ячейка Вороного** $V(p_i)$ - множество точек, ближайших к $p_i$; пересечение $n-1$ полуплоскостей, всегда выпукла
• **Fortune's algorithm** (1987): sweep line + beach line из парабол, два типа событий, $O(N \log N)$ worst-case
• **Двойственность**: вершины Вороного = circumcenters Делоне; рёбра Вороного перпендикулярны рёбрам Делоне
• **ML**: 1-NN decision boundary = диаграмма Вороного; k-means = Lloyd's algorithm = центроидная диаграмма Вороного

Связанные темы

Диаграмма Вороного связывает вычислительную геометрию, ML и робототехнику через единую геометрическую структуру:

• Триангуляция Делоне — двойственная структура: circumcenters Делоне = вершины Вороного
• Выпуклая оболочка — определяет граничные неограниченные ячейки диаграммы Вороного
• Сложность алгоритмов — Fortune O(N log N) - канонический пример преимущества над O(N^2)
• Метрики качества ML — 1-NN boundary = Voronoi; k-means = centroidal Voronoi Tessellation
• Motion Planning — Voronoi roadmap максимизирует клиренс от препятствий

Вопросы для размышления

• Fortune's algorithm использует beach line из парабол - почему именно параболы, а не другие кривые? Как метрика расстояния меняет форму кривых beach line?
• Weighted Voronoi diagram (мультипликативные веса) используется в Uber для учёта времени поездки. Как изменится форма ячеек и алгоритм построения при переходе от евклидовой метрики к взвешенной?
• k-means гарантирует сходимость к локальному минимуму, но не глобальному. Какие конфигурации начальных центроидов приводят к плохим локальным минимумам с точки зрения геометрии Вороного?

Связанные уроки

• cgeom-04
• cgeom-03
• cgeom-02
• cgeom-01
• alg-01-big-o
• ml-05-evaluation
• rob-05