418
правок
Изменения
Нет описания правки
Каждый шаг выполняется за <tex>O(i)</tex>, значит, суммарно диаграмма из <tex>n</tex> сайтов с нуля создаётся за <tex>O(n^2)</tex>.
== Диаграмма <tex>k</tex>-го порядка ==
Ячейка Вороного <tex>k</tex>-го порядка — множество точек, имеющих в качестве ближайших <tex>k</tex> соседей определённое множество из <tex>k</tex> сайтов. Чтобы построить диаграмму <tex>k</tex>-го порядка, нужно взять диаграмму <tex>k - 1</tex>-го порядка для первых <tex>k - 1</tex> сайтов и заменить каждую ячейку на диаграмму Вороного на множестве остальных сайтов.
Диаграмма <tex>n - 1</tex>-го порядка является farthest-point диаграммой, т.е. в каждой её ячейке все точки являются наиболее удалёнными от какого-то сайта.
{|
|[[Файл:voronoi-first-order.png|200px|thumb|Диаграмма первого порядка]]
|[[Файл:voronoi-second-order.png|200px|thumb|Диаграмма второго порядка]]
|[[Файл:voronoi-third-order.png|200px|thumb|Диаграмма третьего порядка]]
|[[Файл:voronoi-tenth-order.png|200px|thumb|Диаграмма десятого порядка, она же farthest-point]]
|}
{{Утверждение
|statement=Сайт имеет ячейку в farthest-point диаграмме тогда и только тогда, когда он является вершиной выпуклой оболочки всех сайтов.
}}
{{Утверждение
|statement=Все ячейки в farthest-point диаграмме неограничены.
}}
Чтобы найти farthest-point диаграмму, сначала найдём выпуклую оболочку всех сайтов. Обозначим сайты, её образующие, через <tex>p_1, p_2, ..., p_m</tex>. Делаем их случайную перестановку, но запомним порядки обхода в выпуклой оболочке по часовой стрелке (<tex>cw(p_i)</tex>) и против часовой (<tex>ccw(p_i)</tex>). Далее удаляем из выпуклой оболочки все точки, кроме первых трёх (запоминая при этом их соседей в оболочке на момент удаления). После этого мы строим farthest-point диаграмму для первых трёх точек и последовательно добавляем остальные (удалённые) в порядке, обратном порядку удаления.
{|
|[[Файл:voronoi-farthest-construct.png|600px|thumb]]
|}
Для точки <tex>p_i</tex> ячейка встанет «между» ячейками, соответствующими <tex>cw(p_i)</tex> и <tex>ccw(p_i)</tex>. Перед добавлением <tex>p_i</tex> <tex>cw(p_i)</tex> и <tex>ccw(p_i)</tex> — соседи, поэтому между ними построен серединный перпендикуляр. Серединный перпендикуляр к <tex>p_i ccw(p_i)</tex> даст новое ребро, которое лежит в farthest-point ячейке <tex>ccw(p_i)</tex> и является частью границы ячейки <tex> p_i</tex>. Обойдём ячейку <tex>ccw(p_i)</tex> по часовой стрелке, чтоб понять, какое ребро пересечёт перпендикуляр. С другой стороны этого ребра лежит ячейка какой-то точки <tex>p_j<tex>, и серединный перпендикуляр <tex>p_i p_j</tex> тоже даст ребро ячейке <tex>p_i</tex>. Аналогично совершим обход и так далее. Последний серединный перпендикуляр будет построен для <tex>p_i cw(p_i)</tex>. После этого удаляем рёбра, которые лежат внутри новой ячейки.
== Источники ==
* de Berg, Cheong, van Kreveld, Overmars. Computational Geometry, Algorithms and Applicants, 2008. ppp. 147-151, 164-166
* [http://students.info.uaic.ro/~emilian.necula/vor2.pdf Инкрементальный алгоритм]
* [http://en.wikipedia.org/wiki/Voronoi_diagram Wikipedia — Voronoi diagram]
* [http://www.cs.uu.nl/docs/vakken/ga/slides7b.pdf — Диаграммы высших порядков]
[[Категория: Вычислительная геометрия]]
