MAXimal

добавлено: 16 Jan 2009 0:58
редактировано: 26 Apr 2011 16:58

Диаграмма Вороного в 2D

Определение

Даны $n$ точек $P_i(x_i,y_i)$ на плоскости. Рассмотрим разбиение плоскости на $n$ областей $V_i$ (называемых многоугольниками Вороного или ячейками Вороного, иногда — многоугольниками близости, ячейками Дирихле, разбиением Тиссена), где $V_i$ — множество всех точек плоскости, которые находятся ближе к точке $P_i$ , чем ко всем остальным точкам $P_k$ :

$V_i = \{ (x,y): \rho ((x,y), P_i) = \min_{ k = 1 [...]$

Само разбиение плоскости называется диаграммой Вороного данного набора точек $P_k$ .

Здесь $\rho(p,q)$ — заданная метрика, обычно это стандартная Евклидова метрика: $\rho(p,q) = \sqrt{ (x_p-x_q)^2 + (y_p-y_q)^2 }$ , однако ниже будет рассмотрен и случай так называемой манхэттенской метрики. Здесь и далее, если не оговорено иного, будет рассматриваться случай Евклидовой метрики

Ячейки Вороного представляют собой выпуклые многоугольники, некоторые являются бесконечными. Точки, принадлежащие согласно определению сразу нескольким ячейкам Вороного, обычно так и относят сразу к нескольким ячейкам (в случае Евклидовой метрики множество таких точек имеет меру нуль; в случае манхэттенской метрики всё несколько сложнее).

Такие многоугольники впервые были глубоко изучены русским математиком Вороным (1868-1908 гг.).

Свойства

Диаграмма Вороного является планарным графом, поэтому она имеет $O(n)$ вершин и рёбер.
Зафиксируем любое $i=1 \ldots n$ . Тогда для каждого $j=1 \ldots n, j \ne i$ проведём прямую — серединный перпендикуляр отрезка $(P_i,P_j)$ ; рассмотрим ту полуплоскость, образуемую этой прямой, в которой лежит точка $P_i$ . Тогда пересечение всех полуплоскостей для каждого $j$ даст ячейку Вороного $P_i$ .
Каждая вершина диаграммы Вороного является центром окружности, проведённой через какие-либо три точки множества $P$ . Эти окружности существенно используются во многих доказательствах, связанных с диаграммами Вороного.
Ячейка Вороного $V_i$ является бесконечной тогда и только тогда, когда точка $P_i$ лежит на границе выпуклой оболочки множества $P_k$ .
Рассмотрим граф, двойственный к диаграмме Вороного, т.е. в этом графе вершинами будут точки $P_i$ , а ребро проводится между точками $P_i$ и $P_j$ , если их ячейки Вороного $V_i$ и $V_j$ имеют общее ребро. Тогда, при условии, что никакие четыре точки не лежат на одной окружности, двойственный к диаграмме Вороного граф является триангуляцией Делоне (обладающей множеством интересных свойств).

Применение

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

В рассмотренных ниже задачах время, необходимое на построение самой диаграммы Вороного, в асимптотиках не учитывается.

Нахождение ближайшей точки для каждой.
Отметим простой факт: если для точки $P_i$ ближайшей является точка $P_j$ , то эта точка $P_j$ имеет "своё" ребро в ячейке $V_i$ . Отсюда следует, что, чтобы найти для каждой точки ближайшую к ней, достаточно просмотреть рёбра её ячейки Вороного. Однако каждое ребро принадлежит ровно двум ячейкам, поэтому будет просмотрено ровно два раза, и вследствие линейности числа рёбер мы получаем решение данной задачи за $O(n)$ .
Нахождение выпуклой оболочки.
Вспомним, что вершина принадлежит выпуклой оболочке тогда и только тогда, когда её ячейка Вороного бесконечна. Тогда найдём в диаграмме Вороного любое бесконечное ребро, и начнём двигаться в каком-либо фиксированном направлении (например, против часовой стрелки) по ячейке, содержащей это ребро, пока не дойдём до следующего бесконечного ребра. Тогда перейдём через это ребро в соседнюю ячейку и продолжим обход. В результате все просмотренные рёбра (кроме бесконечных) будут являться сторонами искомой выпуклой оболочки. Очевидно, время работы алгоритма - $O(n)$ .
Нахождение Евклидова минимального остовного дерева.
Требуется найти минимальное остовное дерево с вершинами в данных точках $P$ , соединяющее все эти точки. Если применять стандартные методы теории графов, то, т.к. граф в данном случае имеет $O(n^2)$ рёбер, даже оптимальный алгоритм будет иметь не меньшую асимптотику.
Рассмотрим граф, двойственный диаграмме Вороного, т.е. триангуляцию Делоне. Можно показать, что нахождение Евклидова минимального остова эквивалентно построению остова триангуляции Делоне. Действительно, в алгоритме Прима каждый раз ищется кратчайшее ребро между двумя можествами точек; если мы зафиксируем точку одного множества, то ближайшая к ней точка имеет ребро в ячейке Вороного, поэтому в триангуляции Делоне будет присутствовать ребро к ближайшей точке, что и требовалось доказать.
Триангуляция является планарным графом, т.е. имеет линейное число рёбер, поэтому к ней можно применить алгоритм Крускала и получить алгоритм с временем работы $O(n \log n)$ .
Нахождение наибольшей пустой окружности.
Требуется найти окружность наибольшего радиуса, не содержащую внутри никакую из точек $P_i$ (центр окружности должен лежать внутри выпуклой оболочки точек $P_i$ ). Заметим, что, т.к. функция наибольшего радиуса окружности в данной точке $f(x,y)$ является строго монотонной внутри каждой ячейки Вороного, то она достигает своего максимума в одной из вершин диаграммы Вороного, либо в точке пересечения рёбер диаграммы и выпуклой оболочки (а число таких точек не более чем в два раза больше числа рёбер диаграммы). Таким образом, остаётся только перебрать указанные точки и для каждой найти ближайшую, т.е. решение за $O(n)$ .

Простой алгоритм построения диаграммы Вороного за $O(n^4)$

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

Рассмотрим здесь самый простой алгоритм, основанный на приведённом выше свойстве, что каждая ячейка Вороного представляет собой пересечение полуплоскостей. Зафиксируем $i$ . Проведём между точкой $P_i$ и каждой точкой $P_j$ прямую — серединный перпендикуляр, затем пересечём попарно все полученные прямые — получим $O(n^2)$ точек, и каждую проверим на принадлежность всем $n$ полуплоскостям. В результате за $O(n^3)$ действий мы получим все вершины ячейки Вороного $V_i$ (их уже будет не более $n$ , поэтому мы можем без ухудшения асимптотики отсортировать их по полярному углу), а всего на построение диаграммы Вороного потребуется $O(n^4)$ действий.

Случай особой метрики

Рассмотрим следующую метрику:

$\rho(p,q) = \max (|x_p-x_q|, |y_p-y_q|)$

Начать рассмотрение следует с разбора простейшего случая — случая двух точек $A$ и $B$ .

Если $A_x=B_x$ или $A_y=B_y$ , то диаграммой Вороного для них будет соответственно вертикальная или горизонтальная прямая.

Иначе диаграмма Вороного будет иметь вид "уголка": отрезок под углом $45$ градусов в прямоугольнике, образованном точками $A$ и $B$ , и горизонтальные/вертикальные лучи из его концов в зависимости от того, длиннее ли вертикальная сторона прямоугольника или горизонтальная.

Особый случай — когда этот прямоугольник имеет одинаковую длину и ширину, т.е. $|A_x-B_x| = |A_y-B_y|$ . В этом случае будут иметься две бесконечные области ("уголки", образованные двумя лучами, параллельными осям), которые по определению должны принадлежать сразу обеим ячейкам. В таком случае дополнительно определяют в условии, как следует понимать эти области (иногда искусственно вводят правило, по которому каждый уголок относят к своей ячейке).

Таким образом, уже для двух точек диаграмма Вороного в данной метрике представляет собой нетривиальный объект, а в случае большего числа точек эти фигуры надо будет уметь быстро пересекать.