Изменения

Перейти к: навигация, поиск

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

8659 байт добавлено, 15:03, 20 января 2020
Алгоритм Чана
{{В разработке}}
 
== Определения ==
=== Совсем неформальное определение ===
=== Неформальное определение ===
Есть множество точек <tex>P</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>.
=== Формальное определение ===
|statement=<tex>\mathcal{V}(p_i) = \bigcap\limits_{1 \leqslant j \leqslant n, j \neq i} h(p_i, p_j)</tex>
}}
Отсюда получаем, что что ячейка Вороного — это пересечение <tex>n - 1</tex> полуплоскостей, и поэтому представляет собой (возможно, неограниченную) открытую выпуклую область с не более чем <tex>n - 1</tex> вершинами и <tex>n - 1</tex> рёбрами.
=== Топология диаграммы Вороного ===
{{Теорема
|statement=Для <tex>n \geqslant 3</tex> сайтов диаграмма Вороного содержит не больше <tex>2n - 5</tex> вершин и <tex> 3n - 6</tex> рёбер.
|proof=[[Файл:voronoi-infinite-vertex.png|200px|right]]Для случая сайтов, лежащих на одной прямой, утверждение напрямую следует из вида диаграммы для этого случая, поэтому рассмотрим общий случай. По [[Формула Эйлера|формуле Эйлера]] <tex>v - e + f = 2</tex>, где <tex>v</tex> — число вершин, <tex>e</tex> — число рёбер и <tex>f</tex> — число граней связного планарного графа. Мы не можем сразу применить эту формулу к <tex>Vor(P)</tex>, потому что в этом графе есть полубесконечные рёбра. Поэтому добавим вершину <tex>n_v_\infty</tex>, и все полубесконечные рёбра мы превратим в рёбра, инцидентные ей. Таким образом мы увеличили число вершин на одну, а число рёбер не изменилось. Число граней равно <tex>n</tex> по определению диаграммы Вороного. Тогда по формуле Эйлера получаем <tex>(v + 1) - e + n = 2</tex>.Сумма степеней всех вершин полученного графа равна <tex>2e</tex>, так как у каждого ребра есть ровно два конца (нет петель). Также у из каждой вершины исходят как минимум три ребра. Отсюда получаем <tex>2e \geqslant 3 (n v + 1)</tex>.
Домножим равенство на два и вычтем из него полученную нижнюю границу для <tex>2 \cdot e</tex>, в результате получим <tex> v \leqslant 2n - 5</tex>. Далее подставим этот результат в равенство и получим <tex>e \leqslant 3n - 6</tex>, что и требовалось доказать.
}}
== Построение ==
=== Наивный алгоритм ===
Будем [[Пересечение полуплоскостей, связь с выпуклыми оболочками|пересекать полуплоскости]] по по [[#intersect|свойству ячейки диаграммы]]. Необходимо <tex>n</tex> раз для каждого сайта пересечь <tex>n - 1</tex> плоскость, что суммарно делается за <tex>O(n^2 \log n)</tex>.
=== Инкрементальный алгоритм ===
Храним диаграмму в [[ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых|РСДС]]. Пусть у нас уже есть диаграмма для точек <tex>p_1, p_2, ..., p_i</tex>. Добавим новый сайт <tex>p_{i+1}</tex>. Сначала [[Локализация в ППЛГ методом полос (персистентные деревья)|найдём]] сайт <tex>p_j</tex>, в ячейку которого попадает <tex>p_{i+1}</tex>, перебором. После этого строим новую ячейку: сначала проведём серединный перпендикуляр для <tex>p_{i+1}p_j</tex>, он пересечёт границу ячейки <tex>\mathcal{V}(p_j)</tex> с ячейкой <tex>\mathcal{V}(p_k)</tex>; на следующем шаге будем строить серединный перпендикуляр для <tex>p_{i+1} p_k</tex> и так далее.
В процессе построения перпендикуляров необходимо обновлять РСДС. Каждый раз, когда новое ребро полуребро <tex>e</tex>, порождаемое <tex>p_{i+1}</tex> и <tex>p_j</tex>, пересекает существовавшее ранее ребро полуребро <tex>e'</tex>, создаётся новая вершина <tex>v</tex> и начинается новое ребро полуребро <tex>e+1</tex>.
Обновление РСДС происходит следующим образом:
* создаём вершину <tex>v</tex> с ребром полуребром <tex>e</tex>;* для ребра полуребра <tex>e</tex> в РСДС второй конец в вершине <tex>v</tex>, следующее ребро полуребро — <tex>e'</tex>, инцидентные грани — слева <tex>\mathcal{V}(i+1)</tex>, справа — <tex>\mathcal{V}(j)</tex>;* добавляем в РСДС ребро полуребро <tex>e + 1</tex> с началом в <tex>v</tex> и предыдущим ребром полуребром <tex>e</tex>;* удаляем все рёбраполурёбра, лежащие между вершиной начала <tex>e</tex> и вершиной конца <tex>e</tex>, по часовой стрелке;* обновляем реброполуребро, соответствующее грани для <tex>\mathcal{V}(p_j)</tex> — им становится <tex>e</tex>.
Каждый шаг выполняется за <tex>O(i)</tex>, значит, суммарно диаграмма из <tex>n</tex> сайтов с нуля создаётся за <tex>O(n^2)</tex>.
|}
== Диаграмма = Алгоритм Форчуна ===Построение производится при помощи заметающей прямой и парабол позади неё (параболы в данном случае - это множества точек, равноудалённых от вершины и прямой). Сама диаграмма "рисуется" местами соприкасания соседних парабол. Несмотря на то, что в теории движение прямой происходит непрерывно, сам алгоритм обрабатывает только крайние случаи, когда происходят события. Рассматривается 2 типа событий - появление новой параболы, когда заметающая прямая касается вершины, и схлопывание параболы - когда две соседние параболы её полностью накрывают. Всего событий <tex>O(n)</tex> (<tex>n</tex> - число вершин). Для каждого события вычисляется его время (позиция заметающей прямой), события кладутся в очередь с приоритетом (отсюда <tex>O(\log n)</tex> по времени) и обрабатываются, пока очередь непуста. При обработке событий также записываются пары взаимодействующих вершин (у которых сайты имеют общую границу), это и является результатом работы алгоритма. Сложность работы алгоритма - <tex>O(n \log n)</tex> по времени и <tex>O(n)</tex> по памяти. Более подробно:* [https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A4%D0%BE%D1%80%D1%87%D1%83%D0%BD%D0%B0 Описание алгоритма на Wikipedia]* [https://www2.cs.sfu.ca/~binay/813.2011/Fortune.pdf Презентация с описанием в деталях] === Алгоритм Чана ===Вершины проецируются из двумерной плоскости на поверхность параболоида (<tex>x, y</tex> остаются те же, добавляется <tex>z = x^2 + y^2</tex>). Далее по ним строится нижняя [[Статические_выпуклые_оболочки:_Джарвис,_Грэхем,_Эндрю,_Чен,_QuickHull|выпуклая оболочка]]. Поскольку параболоид выпуклый, никакие вершины не будут удалены. На выходе получаются рёбра между вершинами, которые соответствуют триангуляции Делоне. Сложность работы - <tex>kO(n \log n)</tex>. == Диаграмма k-го порядка =={{Определение|definition='''Ячейка Вороного ''' <tex>k</tex>'''-го порядка ''' (<tex>\mathcal{V}_k(p_1, p_2, ..., p_k)</tex>) — множество точек, имеющих в качестве ближайших <tex>k</tex> соседей определённое множество из сайтов <tex>kp_1, p_2, ..., p_k</tex> сайтов. }} Чтобы построить диаграмму <tex>k</tex>-го порядка, нужно взять возьмём диаграмму <tex>k - 1</tex>-го порядка и заменить каждую ячейку (она будет . Каждая ячейка построена для некоторого множества набора <tex>P_{k-1}</tex> сайтов. Обозначим множество этих сайтов за <tex>S</tex>. [[Пересечение выпуклых многоугольников|Пересечём]] каждую из этих ячеек с ячейками диаграммы первого порядка, построенной на множестве сайтов <tex>P \setminus S</tex>. Когда мы пересекаем ячейку <tex>k - 1</tex> сайтов) на диаграмму Вороного на множестве остальных сайтов. Заменив её на диаграмму -го порядка для точек <tex>S</tex> с ячейкой первого порядка для остальных сайтовточки <tex>p_i</tex>, мы фактически разделяем её на несколько частей. Каждая новая часть будет частью ячейки Вороного получаем ячейку для какой-то точки не из множества <tex>P_S \cup \{k-1p_i\}</tex>. Но так как в изначальной ячейке все точки являются ближайшими к сайтам из После пересечения ячеек необходимо объединить те, которые отвечают за одинаковый набор сайтов (это могут быть только соседние по ребру ячейки). Итого совершаем <tex>P_{k-1}</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-second-order.png|200px|thumb|Диаграмма второго порядка]]
|[[Файл:voronoi-third-order.png|200px|thumb|Диаграмма третьего порядка]]
|[[Файл:voronoi-tenth-order.png|200px|thumb|Диаграмма десятого <tex>n - 1</tex>-го порядка, (она же farthest-point диаграмма ) для данного набора сайтов]]
|}
== Farthest-point диаграмма ==
{{Определение|definition=Диаграмма <tex>n - 1</tex>-го порядка является '''farthest-point диаграммой''', т.е. в каждой её ячейке все точки являются наиболее удалёнными от какого-то сайта.}} === Свойства ==={{Лемма|statement=Для любой точки <tex>q</tex> плоскости самый удалённый от неё сайт из <tex>P</tex> должен лежать на [[Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull|выпуклой оболочке]] <tex>P</tex>.|proof=[[Файл:voronoi-farthest-inside.png|200px|right]]Сайт, не находящийся на выпуклой оболочке, лежит внутри неё по свойствам выпуклой оболочки. Пусть самый удалённый от точки <tex>q</tex> сайт <tex>p_i</tex> не лежит на выпуклой оболочке (т.е. лежит внутри неё). Проведём луч <tex>q p_i</tex>. Он пересечёт ребро выпуклой оболочки <tex>p_j p_k</tex>. Получатся два смежных угла, рассмотрим тот, который оказался прямым или тупым. Тогда в полученном треугольнике <tex>\rho(q, p_j) > \rho(q, p_i)</tex>, так как напротив большего угла лежит большая сторона. Пришли к противоречию.}} {{Лемма|statement=Сайт, который лежит внутри выпуклой оболочки сайтов, не может иметь ячейку в farthest-point диаграмме.|proof=Пусть это не так и сайт <tex>p</tex> лежит внутри выпуклой оболочки и имеет ячейку в farthest-point диаграмме. Тогда внутри неё есть точка <tex>q</tex>. Но по предыдущей лемме самый удалённый для <tex>q</tex> сайт лежит на выпуклой оболочке, а значит, сайт <tex>p</tex> не может быть самым удалённым для <tex>q</tex>. Пришли к противоречию.}} {{Лемма|statement=Каждый сайт, который является вершиной выпуклой оболочки сайтов, имеет ячейку в farthest-point диаграмме.|proof=Докажем по индукции. База индукции: для двух сайтов они оба являются вершинами выпуклой оболочки и оба имеют ячейку в farthest-point диаграмме (дальняя от сайта полуплоскость). Переход: добавим сайт <tex>p</tex> так, что он станет новой вершиной выпуклой оболочки. Пусть он не имеет ячейку в farthest-point диаграмме, то есть уже имеющаяся перед его добавлением диаграмма не меняется. Для построения farthest-point диаграммы проводятся серединные перпендикуляры между всеми парами сайтов, и полученные полуплоскости пересекаются; раз новой ячейки не добавилось, то серединные перпендикуляры между <tex>p</tex> и остальными сайтами совпали с уже имеющимися перпендикулярами. Это возможно, только если <tex>p</tex> совпал с другим сайтом. Пришли к противоречию.}}
{{Утверждение
|statement=Сайт имеет ячейку в farthest-point диаграмме тогда и только тогда, когда он является вершиной выпуклой оболочки всех сайтов.
|proof=Непосредственно следует из двух предыдущих лемм.
}}
{{Утверждение
|statement=Все ячейки в farthest-point диаграмме неограничены.
|proof=[[Файл:voronoi-farthest-unbounded.png|200px|right]]Пусть <tex>p_i</tex> — сайт на выпуклой оболочке сайтов, а <tex>q</tex> — точка, для которой он является наиболее удалённым. Тогда для всех точек на луче, лежащем на <tex>p_i q</tex>, начинающемся в <tex>q</tex> и не проходящим через <tex>p_i</tex>, сайт <tex>p_i</tex> будет наиболее удалённым среди остальных сайтов. Значит, ячейка сайта <tex>p_i</tex> в farthest-point диаграмме включает в себя этот луч, а значит, неограничена.
}}
=== Алгоритм ===Чтобы найти farthest-point диаграмму, сначала найдём выпуклую оболочку всех сайтов. Обозначим сайты, её образующие, через <tex>p_1, p_2, ..., p_m</tex>. Запомним порядки обхода для каждой вершины выпуклой оболочки по часовой стрелке (<tex>cw(p_i)</tex>) и против часовой (<tex>ccw(p_i)</tex>) и сделаем случайную перестановку точек. Далее удаляем из выпуклой оболочки все точки, кроме первых трёх (запоминая при этом их соседей в оболочке на момент удаления). После этого мы строим farthest-point диаграмму для первых трёх точек (пересекая полуплоскости) и последовательно добавляем остальные (удалённые) в порядке, обратном порядку удаления.
{|
Для точки <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>. После этого удаляем рёбра, которые лежат внутри новой ячейки.
 
== См. также ==
* [[Трапецоидная карта]]
* [[Триангуляция Делоне]]
* [[Straight skeleton]]
== Источники ==
* de Berg, Cheong, van Kreveld, Overmars. Computational Geometry, Algorithms and Applicants, 2008. pp. 147-151, 164-166
* [http://students.info.uaic.ro/~emilian.necula/vor2.pdf Инкрементальный алгоритмAlgorithms for constructing Voronoi diagrams, Vera Sacrist´an {{---}} Incremental algorithm]
* [http://en.wikipedia.org/wiki/Voronoi_diagram Wikipedia — Voronoi diagram]
* [https://web.archive.org/web/20170329014016/http://www.cs.uu.nl/docs/vakken/ga/slides7b.pdf Диаграммы высших порядковComputational Geometry {{---}} Lecture 13: More on Voronoi diagrams]
[[Категория: Вычислительная геометрия]]
[[Категория: Триангуляция Делоне и диаграмма Вороного]]
Анонимный участник

Навигация