Изменения
→Алгоритм Чана
=== Неформальное определение ===Есть множество точек <tex>t^\circP</tex> {{---}} внутренняя часть отрезкана плоскости. Внутренность Кусочек плоскости из точек <tex>q</tex> такой, что для всех <tex>q</tex> ближайшей точкой из множества <tex>P</tex> является одна и та же точка <tex>p</tex>, называется ячейкой Вороного точки {{---}} пустое множество<tex>p</tex>. Разбиение плоскости на такие ячейки для всех точек <tex>p_i \in P</tex> называется диаграммой Вороного для множества <tex>P</tex>.
==Алгоритм=Связь с триангуляцией Делоне ==={{ОпределениеРассмотрим сначала алгоритм для слабо пересекающихся сайтов|definition='''Наибольшая пустая окружность''' точки <tex>q</tex> по отношению к <tex>P</tex> (''largest empty circle of ''<tex>q</tex>'' with respect to ''<tex>P</tex>, а потом обобщим его для случая сильно пересекающихся сайтов<tex>C_P(q)</tex>) — наибольшая окружность с центром в <tex>q</tex> такая, что во внутренности соответствующего ей круга не лежит ни одного сайта из <tex>P</tex>.}}
{{Лемма|statement=Точка <tex>q</tex> — вершина диаграммы Вороного в том и только в том случае, когда <tex>C_P(q)</tex> содержит три и более сайтов на своей границе.|proof==Случай слабо пересекающихся Предположим, что <tex>q</tex> существует, а <tex>p_i, \ p_j, \ p_k</tex> — соответствующие точки. Так как внутри <tex>C_P(q)</tex> нет других сайтов===, а <tex>q</tex> равноудалена от точек <tex>p_i, \ p_j, \ p_k</tex>, <tex>q</tex> должна быть на границе <tex>\mathcal{V}(p_i), \ \mathcal{V}(p_j), \ \mathcal{V}(p_k)</tex> одновременно, то есть вершиной диаграммы.Пусть мы уже построили диаграмму Вороного для некоторого множества Докажем в другую сторону: каждая вершина <tex>q</tex> диаграммы инцидентна минимум трём рёбрам, и, поэтому, как минимум трём ячейкам <tex>\Sigmamathcal{V}(p_i), \ \mathcal{V}(p_j), \ \mathcal{V}(p_k)</tex>. Рассмотрим процедуру вставки нового Тогда <tex>q</tex> лежит на равном расстоянии от <tex>p_i, \ p_j, \ p_k</tex> и не может быть другого сайта ближе к <tex>q</tex>S, так как иначе <tex>\mathcal{V}(p_i), \ \mathcal{V}(p_j), \ \mathcal{V}(p_k)</tex> не сойдутся в <tex>q</tex>.Поэтому можно построить окружность с центром в <tex>q</tex> и <tex>p_i, \ p_j, \ p_k</tex> на границе так, что внутри не будет других сайтов.}}
}}
Чтобы построить диаграмму <tex>k</tex>-го порядка, возьмём диаграмму <tex>k - 1</tex>-го порядка. Каждая ячейка построена для некоторого набора <tex>k-1</tex> сайтов. Обозначим множество этих сайтов за <tex>S</tex>. [[Пересечение выпуклых многоугольников|Пересечём]] каждую из этих ячеек с ячейками диаграммы первого порядка, построенной на множестве сайтов <tex>P \setminus S</tex>. Когда мы пересекаем ячейку <tex>k-1</tex>-го порядка для точек <tex>S</tex> с ячейкой первого порядка для точки <tex>p_i</tex>, получаем ячейку для множества <tex>S \cup \{p_i\}</tex>. После пересечения ячеек необходимо объединить те, которые отвечают за одинаковый набор сайтов (это могут быть только соседние по ребру ячейки). Итого совершаем <tex>k</tex> шагов, на каждом строим <tex>O(n)</tex> диграмм Вороного за время <tex>O(n^3)</tex>, пересекаем <tex>O(n)</tex> ячеек с <tex>O(n)</tex> ячейками за <tex>O(n)</tex> времени, а потом объединяем ячейки за <tex>O(n)</tex> (линейное количество соседних рёбер ячейки, а объединение происходит за <tex>O(1)</tex> за счёт структуры РСДС). Итого <tex>O(k \cdot n^3)</tex>. {||[[Файл:voronoi-first-order.png|200px|thumb|Диаграмма первого порядка]]|[[Файл:voronoi-second-order.png|200px|thumb|Диаграмма второго порядка]]|[[Файл:voronoi-third-order.png|200px|thumb|Диаграмма третьего порядка]]|[[Файл:pathvoronoi-tenth-order.png|250px200px|thumb|rightДиаграмма <tex>n - 1</tex>-го порядка (она же farthest-point диаграмма) для данного набора сайтов]]
|}
[[Категория: Вычислительная геометрия]]
[[Категория: Триангуляция Делоне и диаграмма Вороного]]