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

Источник: e-maxx.ru/algo, страница PDF 262.

정의

given

точек

на плоскости. Рассмотрим разбиение плоскости на

областей

(называемых многоугольниками Вороного или ячейками Вороного, иногда — многоугольниками близости,

ячейками Дирихле, разбиением Тиссена), где

— множество всех точек плоскости, которые находятся ближе к точке

, чем ко всем остальным точкам

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

Здесь

— заданная метрика, обычно это стандартная Евклидова

метрика:

, однако ниже будет рассмотрен и случай так

называемой манхэттенской метрики. Здесь и далее, если не оговорено иного, будет рассматриваться случай

Евклидовой метрики

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

Свойства

● Диаграмма Вороного является планарным 그래프ом, поэтому она имеет

вершин и рёбер.

● Зафиксируем любое

. Тогда для каждого

проведём прямую —

серединный перпендикуляр отрезка

; рассмотрим ту полуплоскость, образуемую этой прямой, в которой

лежит точка

. Тогда пересечение всех полуплоскостей для каждого

даст ячейку Вороного

.

● Каждая vertex диаграммы Вороного является центром окружности, проведённой через какие-либо три точки

множества

. Эти окружности существенно используются во многих доказательствах, связанных с диаграммами Вороного.

● Ячейка Вороного

является бесконечной тогда и только тогда, когда точка

лежит на границе выпуклой

оболочки множества

.

● Рассмотрим 그래프, двойственный к диаграмме Вороного, т.е. в этом 그래프е vertexми будут точки

, а edge

проводится между точками

и

, если их ячейки Вороного

и

имеют общее edge. Тогда, при условии, что

никакие четыре точки не лежат на одной окружности, двойственный к диаграмме Вороного 그래프 является триангуляцией Делоне (обладающей множеством интересных свойств).

Применение

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

● Нахождение ближайшей точки для каждой.

Отметим простой факт: если для точки

ближайшей является точка

, то эта точка

имеет "своё" edge в ячейке

. Отсюда следует, что, чтобы find для каждой точки ближайшую к ней, достаточно просмотреть рёбра её ячейки Вороного. Однако каждое edge принадлежит ровно двум ячейкам, поэтому будет просмотрено ровно два раза, и вследствие линейности числа рёбер мы получаем 해법 данной задачи за .

● Нахождение выпуклой оболочки.

Вспомним, что vertex принадлежит выпуклой оболочке тогда и только тогда, когда её ячейка Вороного бесконечна. Тогда найдём в диаграмме Вороного любое бесконечное edge, и начнём двигаться в каком-либо фиксированном направлении (на예제, против часовой стрелки) по ячейке, содержащей это edge, пока не дойдём до следующего бесконечного ребра. Тогда перейдём через это edge в соседнюю ячейку и продолжим обход. В результате все просмотренные рёбра (кроме бесконечных) будут являться сторонами искомой выпуклой

оболочки. Очевидно, 실행 시간 알고리즘а -

.

● Нахождение Евклидова минимального остовного дерева.

it is required find Minimum spanning tree с vertexми в данных точках , соединяющее все эти точки. Если применять стандартные методы теории 그래프ов, то, т.к. 그래프 в данном случае имеет

рёбер,

даже оптимальный 알고리즘 будет иметь не меньшую асимптотику. Рассмотрим 그래프, двойственный диаграмме Вороного, т.е. триангуляцию Делоне. Можно показать, что нахождение Евклидова минимального остова эквивалентно построению остова триангуляции Делоне. Действительно, в 알고리즘е Прима каждый раз ищется кратчайшее edge между двумя можествами точек; если мы зафиксируем точку одного множества, то ближайшая к ней точка имеет edge в ячейке Вороного, поэтому в триангуляции Делоне будет присутствовать edge к ближайшей точке, что и требовалось доказать. Триангуляция является планарным 그래프ом, т.е. имеет линейное number рёбер, поэтому к ней можно применить

Kruskal's algorithm и получить 알고리즘 с временем работы

.

● Нахождение наибольшей пустой окружности.

it is required find окружность наибольшего радиуса, не содержащую внутри никакую из точек

(центр окружности

должен лежать внутри выпуклой оболочки точек

). Заметим, что, т.к. функция наибольшего радиуса окружности в

данной точке

является строго монотонной внутри каждой ячейки Вороного, то она достигает своего максимума в одной из вершин диаграммы Вороного, либо в точке пересечения рёбер диаграммы и выпуклой оболочки (а number таких точек не более чем в два раза больше числа рёбер диаграммы). Таким образом, остаётся только перебрать указанные точки и для каждой find ближайшую, т.е. 해법 за .

Простой 알고리즘 построения диаграммы Вороного за

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

알고리즘ов, работающих за оптимальную асимптотику

, а некоторые из этих 알고리즘ов даже работают

в среднем за

. Однако все эти 알고리즘ы весьма сложны. Рассмотрим здесь самый простой 알고리즘, основанный на приведённом выше свойстве, что каждая ячейка Вороного представляет собой пересечение полуплоскостей. Зафиксируем

. Проведём между точкой

и каждой

точкой

прямую — серединный перпендикуляр, затем пересечём попарно все полученные прямые — получим

точек, и каждую проверим на принадлежность всем

полуплоскостям. В результате за

действий

мы получим все вершины ячейки Вороного

(их уже будет не более

, поэтому мы можем без ухудшения

асимптотики отсортировать их по полярному углу), а всего на построение диаграммы Вороного поit is required действий.

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

Рассмотрим следующую метрику: Начать рассмотрение следует с разбора простейшего случая — случая двух точек

и

.

Если

или

, то диаграммой Вороного для них будет соответственно вертикальная или горизонтальная прямая. Иначе диаграмма Вороного будет иметь вид "уголка": отрезок под углом

градусов в прямоугольнике,

образованном точками

и

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