Диаграмма Вороного — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Случай сильно пересекающихся сайтов)
м (rollbackEdits.php mass rollback)
 
(не показано 75 промежуточных версий 7 участников)
Строка 1: Строка 1:
==Обозначения и определения==
+
== Определения ==
'''Сайт''' (''site'') {{---}} общее название для точки <tex>p</tex> или замкнутого отрезка <tex>t</tex>.
+
=== Совсем неформальное определение ===
 +
[[Файл:voronoi-diagram.png|200px|thumb|right|Пример диаграммы Вороного]]
 +
Пусть есть карта города, на которой точками обозначены почтовые отделения. Человек хочет отправить письмо, и он пойдёт на ближайшую почту. Ему интересно знать, какое отделение ближе, для любой точки города — необходимость отправить письмо может наступить неожиданно. Для этого он может взять карту и расчертить её на ячейки так, чтобы внутри каждой ячейки находилось только одно отделение, а для всех остальных точек ячейки именно эта почта была ближайшей. Полученная картинка и будет диаграммой Вороного для точек-почт.
  
<tex>t^\circ</tex> {{---}} внутренняя часть отрезка. Внутренность точки {{---}} пустое множество.
+
=== Неформальное определение ===
 +
Есть множество точек <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>.
  
Два замкнутых пересекающихся сайта '''слабо пересекаются''' (''weakly intersect''), если точка их пересечения не принадлежит их внутренностям, то есть они касаются концами.  
+
=== Формальное определение ===
 +
<tex>P = \{ p_1, p_2, ..., p_n\}</tex> — множество точек на плоскости.
  
Два сайта '''сильно пересекаются''' (''strongly intersect''), если точка их пересечения принадлежит внутренности хотя бы одного из данных сайтов.
+
{{Определение
 +
|definition=<tex>p_i \in P</tex> называется '''сайтом''' (''site'').
 +
}}
 +
 
 +
{{Определение
 +
|definition='''Ячейка Вороного''' (''Voronoi cell'', <tex>\mathcal{V}(p_i)</tex>) — множество точек плоскости <tex>q</tex> таких, что для фиксированного сайта <tex>p_i</tex> и любых других сайтов <tex>p_j \in P, \ j \neq i</tex> верно неравенство <tex>\rho(q, p_i) < \rho(q, p_j)</tex>.
 +
}}
 +
 
 +
{{Определение
 +
|definition='''Диаграмма Вороного''' (''Voronoi diagram'', <tex>Vor(P)</tex>) для сайтов <tex>P = \{ p_1, p_2, ..., p_n\}</tex> на плоскости — это разбиение плоскости на ячейки Вороного для каждого сайта из <tex>P</tex>.
 +
}}
 +
 
 +
В зависимости от контекста будем называть диаграммой Вороного как разбиение на ячейки, так и [[Основные определения теории графов|граф]] из вершин и рёбер, составляющих эти ячейки.
 +
 
 +
== Свойства ==
 +
=== Связь с пересечением полуплоскостей ===
 +
Возьмём две точки плоскости: <tex>p</tex> и <tex>q</tex>. Проведём серединный перпендикуляр к отрезку <tex>pq</tex>; полученную полуплоскость, которая содержит в себе <tex>p</tex>, обозначим <tex>h(p, q)</tex>, другую — <tex>h(q, p)</tex>. Заметим, что для точки <tex>r</tex> выполняется <tex>r \in h(p, q)</tex> тогда и только тогда, когда <tex>\rho(r, p) < \rho(r, q)</tex>. Отсюда вытекает следующее:
 +
{{Утверждение
 +
|id=intersect
 +
|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>P</tex> — множество из <tex>n</tex> сайтов. Если они все лежат на одной прямой, то <tex>Vor(P)</tex> представляет собой <tex>n - 1</tex> параллельную прямую. Иначе <tex>Vor(P)</tex> связная и все её рёбра — либо отрезки, либо лучи.
 +
|proof=[[Файл:voronoi-not-lines.png|200px|right]] В случае, если все сайты лежат на одной прямой, каждая пара соседних сайтов порождает серединный перпендикуляр к отрезку, содержащему их, и, соответственно, к прямой, которая содержит все сайты. Так получаются <tex>n - 1</tex> прямая, каждая из которых перпендикулярна прямой, содержащей сайты, а значит, эти прямые параллельны.
  
Расстояние от точки <tex>x \in \mathbb{E}^2</tex> до замкнутого сайта <tex>S_i</tex>: <tex>\delta(x, S_i) = \min{\{||x - y|| : y \in S_i\}}</tex>.
+
Рассмотрим теперь случай, когда сайты не лежат на одной прямой. Покажем, что рёбра — это отрезки или лучи, от противного. Предположим, что есть ребро <tex>e</tex>, являющееся прямой. Пусть оно — граница ячеек <tex>\mathcal{V}(p_i)</tex> и <tex>\mathcal{V}(p_j)</tex>. Пусть точка <tex>p_k \in P</tex> не лежит на прямой <tex>p_i p_j</tex> (по условию такая точка существует). Тогда серединный перпендикуляр к <tex>p_j p_k</tex> не параллелен <tex>e</tex>, и, значит, он его пересекает. Но тогда та часть <tex>e</tex>, что лежит в <tex>h(p_k, p_j)</tex>, не может быть границей <tex>\mathcal{V}(p_j)</tex>, потому что она ближе к <tex>p_k</tex>, чем к <tex>p_j</tex>. Пришли к противоречию.
  
Пусть <tex>H_{ij} = \{x \in \mathbb{E}^2 : \delta(x, S_i) \le \delta(x, S_j)\}</tex>. '''Ячейка Вороного''' (''Voronoi cell'') <tex>V(S_i, \Sigma)</tex> {{---}} множество точек, которые находятся ближе к <tex>S_i</tex>, чем к любому другому сайту, то есть <tex>V(S_i, \Sigma) = \cap_{i \ne j}H_{ij}</tex>.
+
Докажем теперь, что диаграмма связна. Предположим, что это не так. Тогда на её рёбрах найдутся две точки <tex>s</tex> и <tex>t</tex>, между которыми нет пути по рёбрам диаграммы. Рассмотрим отрезок <tex>st</tex>. Он пересекает некоторое количество ячеек диаграммы. Пусть он пересекает какую-то ячейку в точках <tex>a</tex> и <tex>b</tex>. От точки <tex>a</tex> до точки <tex>b</tex> можно добраться по рёбрам тогда и только тогда, когда ячейка связна. Раз пути из <tex>s</tex> в <tex>t</tex> нет, то какая-то из ячеек, пересекаемых отрезком <tex>st</tex>, несвязная. Это возможно, только если она представляет собой полосу, ограниченную двумя параллельными прямыми. Но в нашем случае в диаграмме не может быть прямых, пришли к противоречию.
  
'''Ребро Вороного''' (''Voronoi edge'') {{---}} связное множество точек, принадлежащих пересечению ровно двух ячеек Вороного.
+
[[Файл:voronoi-connected.png|500px]]
 +
}}
  
'''Вершина Вороного''' (''Voronoi vertex'') {{---}} точка, которая принадлежит хотя бы трём ячейкам Вороного.  
+
=== Размер структуры ===
 +
{{Теорема
 +
|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>v_\infty</tex>, и все полубесконечные рёбра мы превратим в рёбра, инцидентные ей. Таким образом мы увеличили число вершин на одну, а число рёбер не изменилось. Число граней равно <tex>n</tex> по определению диаграммы Вороного. Тогда по формуле Эйлера получаем <tex>(v + 1) - e + n = 2</tex>.
 +
Сумма степеней всех вершин полученного графа равна <tex>2e</tex>, так как у каждого ребра есть ровно два конца (нет петель). Также из каждой вершины исходят как минимум три ребра. Отсюда получаем <tex>2e \geqslant 3 (v + 1)</tex>.
 +
Домножим равенство на два и вычтем из него полученную нижнюю границу для <tex>2 \cdot e</tex>, в результате получим <tex> v \leqslant 2n - 5</tex>. Далее подставим этот результат в равенство и получим <tex>e \leqslant 3n - 6</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>\mathcal{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>, так как иначе <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> на границе так, что внутри не будет других сайтов.
 +
}}
 +
 
 +
{{Лемма
 +
|statement=Серединный перпендикуляр к отрезку <tex>p_i p_j</tex> образует ребро диаграммы Вороного в том и только в том случае, если на нём есть точка <tex>q</tex> такая, что <tex>C_P(q)</tex> содержит на своей границе только сайты <tex>p_i, \ p_j</tex>.
 +
|proof=[[Файл:voronoi-circles.png|200px|right]]Предположим, что <tex>q</tex> существует. Тогда, так как <tex>C_P(q)</tex> не содержит в себе сайтов и содержит <tex>p_i, \ p_j</tex> на границе, <tex> \rho(q, p_i) = \rho(q, p_j) \leqslant \rho(q, p_k), \ 1 \leqslant k \leqslant n</tex>. Отсюда выходит, что <tex>q</tex> — вершина <tex>Vor(P)</tex> или лежит на ребре диаграммы. Но по предыдущей лемме выходит, что <tex>q</tex> не может быть вершиной диаграммы. Значит, она лежит на ребре, заданном серединным перпендикуляром к <tex>p_i p_j</tex>.
  
'''Диаграмма Вороного''' (''Voronoi diagram'') <tex>V(\Sigma)</tex> множества сайтов <tex>\Sigma</tex> {{---}} разбиение плоскости на вершины, рёбра и ячейки Вороного.
+
Докажем в другую сторону: пусть серединный перпендикуляр к <tex>p_i p_j</tex> задаёт ребро диаграммы. Наибольшая пустая окружность любой точки <tex>q</tex> на этом ребре должна содержать на границе <tex>p_i</tex> и <tex>p_j</tex> (так как <tex>q</tex> равноудалена от <tex>p_i</tex> и <tex>p_j</tex>). Также эта окружность не должна содержать никаких других сайтов на границе, так как тогда она не является вершиной.
 +
}}
  
'''1-каркас''' (''1-skeleton'') <tex>V_1(\Sigma)</tex> {{---}} набор вершин и рёбер Вороного.
+
{{Теорема
 +
|statement=Если соединить все сайты, соответствующие смежным ячейкам диаграммы Вороного, получится [[триангуляция Делоне]] для этого множества точек.
 +
|proof=Если ячейки, соответствующие сайтам <tex>p_i, \ p_j</tex>, смежны, то серединный перпендикуляр к отрезку <tex>p_i p_j</tex> образует ребро диаграммы Вороного, то есть к нему применима предыдущая лемма и можно построить окружность с <tex>p_i</tex> и <tex>p_j</tex> на границе, внутри которой не будет других сайтов. Триангуляции Делоне принадлежат [[Триангуляция Делоне#Критерий Делоне для рёбер|те и только те]] рёбра (с поправкой на точки, лежащие на одной окружности), на которых можно построить такую окружность, что внутри неё не будет лежать никаких точек. Тогда ребро <tex>p_i p_j</tex> является ребром триангуляции Делоне. За счёт равносильности в обеих используемых леммах мы добавим все рёбра и не построим лишних.
 +
}}
  
В процессе работы алгоритма множество сайтов, которые подаются на вход, может измениться. Чтобы различать начальное и конечное множество сайтов, будем обозначать входное множество через <tex>\Sigma_I</tex>, а множество сайтов, которые присутствуют на результирующей диаграмме Вороного, через <tex>\Sigma</tex>. <tex>\Sigma_I</tex> всегда состоит из замкнутых сайтов, а <tex>\Sigma</tex> {{---}} из точек и открытых отрезков.
+
== Построение ==
 +
=== Наивный алгоритм ===
 +
Будем [[Пересечение полуплоскостей, связь с выпуклыми оболочками|пересекать полуплоскости]] по [[#intersect|свойству ячейки диаграммы]]. Необходимо для каждого сайта пересечь <tex>n - 1</tex> плоскость, что суммарно делается за <tex>O(n^2 \log n)</tex>.
  
Пусть сайты <tex>S_i</tex> и <tex>S_j</tex> слабо пересекаются. Тогда '''битангентная окружность Вороного''' (''bitangent Voronoi circle'') <tex>C_{ij}</tex> {{---}} окружность, касающаяся одновременно <tex>S_i</tex> и <tex>S_j</tex>. При рассмотрении трёх сайтов <tex>S_i</tex>, <tex>S_j</tex> и <tex>S_k</tex>, окружность, касающаяся всех трёх сайтов, называется '''тритангентной окружностью Вороного''' (''tritangent Voronoi circle''). Точки, принадлежащие рёбрам Вороного, являются центрами битангентных окружностей, а вершины {{---}} тритангентных.
+
=== Инкрементальный алгоритм ===
 +
Храним диаграмму в [[ППЛГ и РСДС (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>S \notin \Sigma_I</tex>. Будем говорить, что <tex>S</tex> '''конфликтует''' с окружностью Вороного <tex>C</tex>, если <tex>S</tex> пересекается с кругом, ограниченным <tex>C</tex>. Также <tex>S</tex> конфликтует с ребром <tex>e \in V(S, \Sigma)</tex>, если он пересекается с кругом, ограниченным одной из окружностей Вороного с центром в точке, принадлежащей <tex>e</tex>. '''Область конфликтов''' (''conflict region'') <tex>R_\Sigma(S)</tex> {{---}} множество точек 1-каркаса <tex>V_1(\Sigma)</tex>, соответствующих окружностям Вороного, которые конфликтуют с <tex>S</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>\Sigma</tex>. Рассмотрим процедуру вставки нового сайта <tex>S</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>.
  
'''1'''. Найти первый конфликт сайта <tex>S</tex> с каркасом <tex>V_1(\Sigma)</tex>.
+
{|
 +
|[[Файл:voronoi-incremental-zero-step.png|200px|thumb|Локализация]]
 +
|[[Файл:voronoi-incremental-first-step.png|200px|thumb|Добавление первого ребра]]
 +
|[[Файл:voronoi-incremental.png|200px|thumb|Добавление третьего ребра]]
 +
|[[Файл:voronoi-update-dcel.png|400px|thumb|Обновление структуры при добавлении ребра]]
 +
|}
  
'''2'''. Найти всю область конфликтов сайта <tex>S</tex> c каркасом <tex>V_1(\Sigma)</tex>.
+
=== Алгоритм Форчуна ===
 +
Построение производится при помощи заметающей прямой и парабол позади неё (параболы в данном случае - это множества точек, равноудалённых от вершины и прямой). Сама диаграмма "рисуется" местами соприкасания соседних парабол. Несмотря на то, что в теории движение прямой происходит непрерывно, сам алгоритм обрабатывает только крайние случаи, когда происходят события. Рассматривается 2 типа событий - появление новой параболы, когда заметающая прямая касается вершины, и схлопывание параболы - когда две соседние параболы её полностью накрывают. Всего событий <tex>O(n)</tex> (<tex>n</tex> - число вершин). Для каждого события вычисляется его время (позиция заметающей прямой), события кладутся в очередь с приоритетом (отсюда <tex>O(\log n)</tex> по времени) и обрабатываются, пока очередь непуста. При обработке событий также записываются пары взаимодействующих вершин (у которых сайты имеют общую границу), это и является результатом работы алгоритма.
  
'''3'''. Построить диаграмму Вороного для <tex>\Sigma \cup \{S\} </tex>.
+
Сложность работы алгоритма - <tex>O(n \log n)</tex> по времени и <tex>O(n)</tex> по памяти.
  
'''4'''. Обновить локализационную структуру.
+
Более подробно:
 +
* [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 Презентация с описанием в деталях]
  
{{Лемма
+
=== Алгоритм Чана ===
|statement=
+
Вершины проецируются из двумерной плоскости на поверхность параболоида (<tex>x, y</tex> остаются те же, добавляется <tex>z = x^2 + y^2</tex>). Далее по ним строится нижняя [[Статические_выпуклые_оболочки:_Джарвис,_Грэхем,_Эндрю,_Чен,_QuickHull|выпуклая оболочка]]. Поскольку параболоид выпуклый, никакие вершины не будут удалены. На выходе получаются рёбра между вершинами, которые соответствуют триангуляции Делоне. Сложность работы - <tex>O(n \log n)</tex>.
<tex>\Sigma</tex> {{---}} слабо пересекающееся между собой множество сайтов. Тогда <tex>\forall s \in \Sigma</tex> ячейки Вороного <tex>V(s, \Sigma)</tex> {{---}} односвязные множества.
 
|proof=
 
Для начала докажем, что ячейки связны. Пусть это не так и у ячейки <tex>V(s, \Sigma)</tex> несколько компонент связности. Рассмотрим <tex>\varepsilon</tex> {{---}} одну из тех, которая не содержит в себе <tex>s</tex>. Начнём идти по кратчайшему пути <tex>P</tex> от любой точки <tex>p \in \varepsilon</tex> до <tex>s</tex>. Так как <tex>p</tex> и <tex>s</tex> лежат в разных компонентах связности, найдётся <tex>s' \in \Sigma</tex>, такой что путь <tex>P</tex> проходит через <tex>V(s', \Sigma)</tex>. Значит существует путь от <tex>p</tex> до <tex>s'</tex>, который короче, чем <tex>P</tex>, следовательно и <tex>\delta(p, s') < \delta(p, s) = |P|</tex>. Противоречие.
 
  
Теперь допустим, что <tex>V(s, \Sigma)</tex> содержит разрыв в виде другой ячейки <tex>V(s', \Sigma)</tex>. Проведём прямую, которая соответствует кратчайшему расстоянию между <tex>s</tex> и <tex>s'</tex> и рассмотрим точку <tex>p</tex>, которая лежит на её продолжении за <tex>s'</tex> и принадлежит <tex>V(s, \Sigma)</tex>. Такая точка будет существовать, т.к. <tex>V(s', \Sigma)</tex> лежит внутри <tex>V(s, \Sigma)</tex>. Получаем, что кратчайший путь от <tex>p</tex> до <tex>s</tex> проходит через <tex>s'</tex>. Опять противоречие.
+
== Диаграмма k-го порядка ==
 +
{{Определение
 +
|definition='''Ячейка Вороного''' <tex>k</tex>'''-го порядка''' (<tex>\mathcal{V}_k(p_1, p_2, ..., p_k)</tex>) — множество точек, имеющих в качестве ближайших <tex>k</tex> соседей множество сайтов <tex>p_1, p_2, ..., p_k</tex>.
 
}}
 
}}
  
{|border="0" width="100%"
+
Чтобы построить диаграмму <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>. После пересечения ячеек необходимо объединить те, которые отвечают за одинаковый набор сайтов (это могут быть только соседние по ребру ячейки).
|{{Теорема
+
 
|statement=
+
Итого совершаем <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>.
Пусть <tex>\Sigma</tex> {{---}} множество слабо пересекающихся сайтов, <tex>s</tex> {{---}} сайт, <tex>s \notin \Sigma</tex>. Тогда <tex>R_\Sigma(s)</tex> {{---}} связное непустое множество.
+
 
|proof=
+
{|
Пусть <tex>C = V(s, \Sigma \cup \{s\})</tex>, <tex>R_\Sigma(s) = \varepsilon</tex>.  
+
|[[Файл:voronoi-first-order.png|200px|thumb|Диаграмма первого порядка]]
 +
|[[Файл: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 диаграммой''', т.е. в каждой её ячейке все точки являются наиболее удалёнными от какого-то сайта.
 +
}}
  
Заметим, что <tex>\varepsilon = V_1(\Sigma) \cap C</tex>. Если бы область конфликтов <tex>\varepsilon</tex> была пустой, то было бы верно <tex>C \subset V(q, \Sigma \cup \{p\})</tex> для некоторого <tex>q \in \Sigma</tex> и <tex>V(q, \Sigma \cup s)</tex> не было бы односвязным.
+
=== Свойства ===
 +
{{Лемма
 +
|statement=Для любой точки <tex>q</tex> плоскости самый удалённый от неё сайт из <tex>P</tex> должен лежать на [[Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull|выпуклой оболочке]] <tex>P</tex>.
 +
|proof=[[Файл:voronoi-farthest-inside.png|200px|right]]Сайт, не находящийся на выпуклой оболочке, лежит внутри неё по свойствам выпуклой оболочки.
  
Пусть <tex>\varepsilon_1, \varepsilon_2, ... , \varepsilon_k</tex> {{---}} связные компоненты <tex>\varepsilon</tex> для некоторого <tex>k</tex>.
+
Пусть самый удалённый от точки <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>, так как напротив большего угла лежит большая сторона. Пришли к противоречию.
 +
}}
  
Предположим, что <tex>k \ge 2</tex>. Тогда cуществует путь <tex>P \subseteq C \setminus \varepsilon</tex>, соединяющий две точки <tex>x</tex> и <tex>y</tex> на границе <tex>C</tex> и отделяющий <tex>\varepsilon_1</tex> от <tex>\varepsilon_2</tex>(см. рисунок). <tex>P \cap \varepsilon = \varnothing \Rightarrow P \cap V_1(\Sigma) = \varnothing \Rightarrow P \subseteq intV(q, \Sigma)</tex> для некоторого <tex>q \in \Sigma</tex>. <tex>x, y \in P \Rightarrow</tex> все достаточно малые окрестности <tex>U(x)</tex>, <tex>U(y)</tex> полностью содержатся в <tex>V(q, \Sigma)</tex>. Значит, точки пересечения этих окрестностей с дополнением <tex>C</tex> лежат в <tex>V(q, \Sigma \cup s)</tex> и могут быть соединены путём <tex>L \subseteq V(q, \Sigma \cup \{s\}) \subseteq V(q, \Sigma)</tex>. Следовательно, цикл <tex>P \circ L</tex> полностью содержится в <tex>V(q, \Sigma)</tex> и содержит <tex>\varepsilon_1</tex> или <tex>\varepsilon_2</tex> в своей внутренней части. Это противоречит тому, что <tex>V(q, \Sigma)</tex> {{---}} односвязное множество, следовательно <tex>k = 1</tex>.
+
{{Лемма
 +
|statement=Сайт, который лежит внутри выпуклой оболочки сайтов, не может иметь ячейку в farthest-point диаграмме.
 +
|proof=Пусть это не так и сайт <tex>p</tex> лежит внутри выпуклой оболочки и имеет ячейку в farthest-point диаграмме. Тогда внутри неё есть точка <tex>q</tex>. Но по предыдущей лемме самый удалённый для <tex>q</tex> сайт лежит на выпуклой оболочке, а значит, сайт <tex>p</tex> не может быть самым удалённым для <tex>q</tex>. Пришли к противоречию.
 
}}
 
}}
|[[Файл:path.png|250px|thumb|right]]
 
|}
 
  
Таким образом, для нахождения области конфликтов, можно найти одно конфликтующее ребро, а затем, при помощи DFS, найти все остальные.
+
{{Лемма
 +
|statement=Каждый сайт, который является вершиной выпуклой оболочки сайтов, имеет ячейку в farthest-point диаграмме.
 +
|proof=Докажем по индукции.
 +
 
 +
База индукции: для двух сайтов они оба являются вершинами выпуклой оболочки и оба имеют ячейку в farthest-point диаграмме (дальняя от сайта полуплоскость).
  
Пусть сайт <tex>S</tex> {{---}} это точка <tex>p</tex>.
+
Переход: добавим сайт <tex>p</tex> так, что он станет новой вершиной выпуклой оболочки. Пусть он не имеет ячейку в farthest-point диаграмме, то есть уже имеющаяся перед его добавлением диаграмма не меняется. Для построения farthest-point диаграммы проводятся серединные перпендикуляры между всеми парами сайтов, и полученные полуплоскости пересекаются; раз новой ячейки не добавилось, то серединные перпендикуляры между <tex>p</tex> и остальными сайтами совпали с уже имеющимися перпендикулярами. Это возможно, только если <tex>p</tex> совпал с другим сайтом. Пришли к противоречию.
 +
}}
  
Первый шаг алгоритма начинается с поиска ближайшего соседа <tex>N_\Sigma(p)</tex> точки p среди сайтов <tex>\Sigma</tex> (если есть несколько ближайших, то подойдёт любой из них). Будем хранить нашу диаграмму в скип-листе для того, чтобы можно было быстро выполнять эти запросы. Либо <tex>N_\Sigma(p)</tex> и <tex>p</tex> {{---}} это одна и та же точка, и ничего делать не нужно, либо <tex>p</tex> конфликтует хотя бы с одним ребром, принадлежащим границе ячейки <tex>V(N_\Sigma(p))</tex>. Тогда первый шаг завершается рассмотрением границы <tex>V(N_\Sigma(p))</tex> и возвращением одного из рёбер, конфликтующих с <tex>p</tex>. Как было сказано раньше, второй шаг {{---}} DFS по рёбрам <tex>V_1(\Sigma)</tex> с целью найти все рёбра, конфликтующие с точкой <tex>p</tex>. Теперь, зная <tex>R_\Sigma(p)</tex>, можно создать новую ячейку Вороного <tex>V(S, \Sigma \cup \{S\})</tex> (а как это сделать, я не очень понимаю).
+
{{Утверждение
 +
|statement=Сайт имеет ячейку в farthest-point диаграмме тогда и только тогда, когда он является вершиной выпуклой оболочки всех сайтов.
 +
|proof=Непосредственно следует из двух предыдущих лемм.
 +
}}
  
Если же <tex>S</tex> {{---}} это замкнутый отрезок <tex>t</tex>, то сначала вставляем конечные точки <tex>p'_t</tex> и <tex>p''_t</tex>, используя процедуру, описанную выше. Остаётся вставить открытый отрезок <tex>t^\circ</tex>. Так как <tex>p'_t</tex> и <tex>p''_t</tex> {{---}} соседи <tex>t^\circ</tex> в диаграмме <tex>V(\Sigma \cup \{p'_t, p''_t, t^\circ\})</tex>, <tex>t^\circ</tex> обязан конфликтовать с каким-нибудь ребром ячейки, соответствующей <tex>p'_t</tex> или <tex>p''_t</tex>. Таким образом, первый конфликт <tex>t^\circ</tex> с <tex>V_1(\Sigma \cup \{p'_t, p''_t\})</tex> можно найти, просматривая рёбра ячейки <tex>V(p'_t, \Sigma \cup \{p'_t, p''_t\})</tex> или <tex>V(p''_t, \Sigma \cup \{p'_t, p''_t\})</tex>, то есть, можно опустить шаг поиска ближайшего соседа. Остаётся найти всю область конфликтов, как и в случае с точкой.
+
{{Утверждение
 +
|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 диаграмме включает в себя этот луч, а значит, неограничена.
 +
}}
  
===Случай сильно пересекающихся сайтов===
+
=== Алгоритм ===
{|border="0" width="100%"
+
Чтобы найти farthest-point диаграмму, сначала найдём выпуклую оболочку всех сайтов. Обозначим сайты, её образующие, через <tex>p_1, p_2, ..., p_m</tex>. Запомним порядки обхода для каждой вершины выпуклой оболочки по часовой стрелке (<tex>cw(p_i)</tex>) и против часовой (<tex>ccw(p_i)</tex>) и сделаем случайную перестановку точек. Далее удаляем из выпуклой оболочки все точки, кроме первых трёх (запоминая при этом их соседей в оболочке на момент удаления). После этого строим farthest-point диаграмму для первых трёх точек (пересекая полуплоскости) и последовательно добавляем остальные (удалённые) в порядке, обратном порядку удаления.
|Пусть <tex>p</tex> {{---}} точка, которая сильно пересекается с отрезком <tex>t_i</tex>, т.е. <tex>p \in t^\circ</tex>. Понятно, что <tex>t^\circ</tex> будет ближайшим соседом <tex>p</tex> в <tex>\Sigma</tex>. Пусть <tex>e'_i(p)</tex> и <tex>e''_i(p)</tex> {{---}} два ребра <tex>V(t^\circ, \Sigma)</tex>, которые пересекаются с нормалями к <tex>t</tex>, проведёнными из точки <tex>p</tex> (см. рисунок). Пусть <tex>v'_i(p)</tex> и <tex>v''_i(p)</tex> {{---}} точки пересечения нормалей с рёбрами <tex>e'_i(p)</tex> и <tex>e''_i(p)</tex> соответственно. Тогда алгоритм вставки точки <tex>p</tex> в диаграмму <tex>V(\Sigma)</tex> будет выглядеть следующим образом:
 
  
Начинаем с поиска ближайшего соседа <tex>N_\Sigma(p)</tex>. Если <tex>N_\Sigma(p) = p</tex>, то ничего не делаем. Если <tex>N_\Sigma(p)</tex> {{---}} точка, или отрезок, с которым <tex>p</tex> не пересекается, то запускается процедура вставки, которая была описана выше. Иначе  <tex>N_\Sigma(p) = t_i^\circ</tex> {{---}} отрезок, пересекающийся с <tex>p</tex>. Сначала добавляем <tex>p</tex> в <tex>\Sigma</tex> и заменяем <tex>t_i^\circ</tex> двумя отрезками <tex>p'_ip</tex> и <tex>pp''_i</tex>, где <tex>p'_i</tex> и <tex>p''_i</tex> {{---}} конечные точки <tex>t_i</tex>. Затем ищем рёбра <tex>e'_i(p)</tex> и <tex>e''_i(p)</tex>, разбиваем их в точках <tex>v'_i(p)</tex> и <tex>v''_i(p)</tex> и добавляем отрезки <tex>v'_i(p)p</tex> и <tex>v''_i(p)p</tex> в диаграмму.
+
{|
||[[Файл:strongly_intersect.png|300px|thumb|right]]
+
|[[Файл:voronoi-farthest-construct.png|600px|thumb|Построение очередной ячейки farthest-point диаграммы]]
 
|}
 
|}
  
Если же мы хотим вставить в диаграмму отрезок <tex>t</tex>, то вставляем сначала его крайние точки <tex>p'_t</tex> и <tex>p''_t</tex>. Затем, начиная с <tex>p'_t</tex>, ищем первый конфликт <tex>t^\circ</tex> с текущей диаграммой Вороного и ищем всю область конфликтов. Во время этого поиска, прежде чем тестировать ребро Вороного <tex>e</tex> существующей диаграммы на потенциальный конфликт, мы проверяем, не пересекается ли <tex>t^\circ</tex> с одним из сайтов, связанных с <tex>e</tex>. Если такой сайт <tex>S_i</tex> найден, то поиск останавливается. Если <tex>S_i</tex> {{---}} точка, <tex>p_i</tex>, то вставляем отрезки <tex>p'_tp_i</tex> и <tex>p_ip''_t</tex> рекурсивно. Если <tex>S_i</tex> {{---}} отрезок <tex>t^\circ_i</tex>, то сначала проверяем, не принадлежит ли  один из <tex>t^\circ</tex>, <tex>t^\circ_i</tex> другому. Если так и есть, то прекращаем работу, иначе вычисляем точку пересечения <tex>p_+</tex> отрезков <tex>t^\circ</tex> и <tex>t^\circ_i</tex>, вставляем её в диаграмму, а затем рекурсивно вставляем отрезки <tex>p'_tp_+</tex> и <tex>p_+p''_t</tex>.
+
Для точки <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>. После этого удаляем рёбра, которые лежат внутри новой ячейки.
  
Время работы данного алгоритма составляет <tex>O((n + m)\log^2m)</tex>, где <tex>n</tex> {{---}} количество элементов во входном множестве <tex>\Sigma_I</tex>, а <tex>m</tex> {{---}} количество пар сильно пересекающихся сайтов.
+
== См. также ==
 +
* [[Трапецоидная карта]]
 +
* [[Триангуляция Делоне]]
 +
* [[Straight skeleton]]
  
==Ссылки==
+
== Источники ==
* [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.112.8990&rep=rep1&type=pdf ''Menalaos I. Karavelas'' A robust and efficient implementation for the segment Voronoi diagram.]
+
* de Berg, Cheong, van Kreveld, Overmars. Computational Geometry, Algorithms and Applicants, 2008. pp. 147-151, 164-166
* [http://www.sciencedirect.com/science/article/pii/0925772193900333/pdf?md5=ce44776db4922c6579a191a7c7ada933&pid=1-s2.0-0925772193900333-main.pdf ''Rolf Klein'' Randomized incremental construction of abstract Voronoi diagrams.]
+
* [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]
  
 
[[Категория: Вычислительная геометрия]]
 
[[Категория: Вычислительная геометрия]]
 +
[[Категория: Триангуляция Делоне и диаграмма Вороного]]

Текущая версия на 19:26, 4 сентября 2022

Определения

Совсем неформальное определение

Пример диаграммы Вороного

Пусть есть карта города, на которой точками обозначены почтовые отделения. Человек хочет отправить письмо, и он пойдёт на ближайшую почту. Ему интересно знать, какое отделение ближе, для любой точки города — необходимость отправить письмо может наступить неожиданно. Для этого он может взять карту и расчертить её на ячейки так, чтобы внутри каждой ячейки находилось только одно отделение, а для всех остальных точек ячейки именно эта почта была ближайшей. Полученная картинка и будет диаграммой Вороного для точек-почт.

Неформальное определение

Есть множество точек [math]P[/math] на плоскости. Кусочек плоскости из точек [math]q[/math] такой, что для всех [math]q[/math] ближайшей точкой из множества [math]P[/math] является одна и та же точка [math]p[/math], называется ячейкой Вороного точки [math]p[/math]. Разбиение плоскости на такие ячейки для всех точек [math]p_i \in P[/math] называется диаграммой Вороного для множества [math]P[/math].

Формальное определение

[math]P = \{ p_1, p_2, ..., p_n\}[/math] — множество точек на плоскости.


Определение:
[math]p_i \in P[/math] называется сайтом (site).


Определение:
Ячейка Вороного (Voronoi cell, [math]\mathcal{V}(p_i)[/math]) — множество точек плоскости [math]q[/math] таких, что для фиксированного сайта [math]p_i[/math] и любых других сайтов [math]p_j \in P, \ j \neq i[/math] верно неравенство [math]\rho(q, p_i) \lt \rho(q, p_j)[/math].


Определение:
Диаграмма Вороного (Voronoi diagram, [math]Vor(P)[/math]) для сайтов [math]P = \{ p_1, p_2, ..., p_n\}[/math] на плоскости — это разбиение плоскости на ячейки Вороного для каждого сайта из [math]P[/math].


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

Свойства

Связь с пересечением полуплоскостей

Возьмём две точки плоскости: [math]p[/math] и [math]q[/math]. Проведём серединный перпендикуляр к отрезку [math]pq[/math]; полученную полуплоскость, которая содержит в себе [math]p[/math], обозначим [math]h(p, q)[/math], другую — [math]h(q, p)[/math]. Заметим, что для точки [math]r[/math] выполняется [math]r \in h(p, q)[/math] тогда и только тогда, когда [math]\rho(r, p) \lt \rho(r, q)[/math]. Отсюда вытекает следующее:

Утверждение:
[math]\mathcal{V}(p_i) = \bigcap\limits_{1 \leqslant j \leqslant n, j \neq i} h(p_i, p_j)[/math]

Отсюда получаем, что ячейка Вороного — это пересечение [math]n - 1[/math] полуплоскостей, и поэтому представляет собой (возможно, неограниченную) открытую выпуклую область с не более чем [math]n - 1[/math] вершинами и [math]n - 1[/math] рёбрами.

Топология диаграммы Вороного

Теорема:
Пусть [math]P[/math] — множество из [math]n[/math] сайтов. Если они все лежат на одной прямой, то [math]Vor(P)[/math] представляет собой [math]n - 1[/math] параллельную прямую. Иначе [math]Vor(P)[/math] связная и все её рёбра — либо отрезки, либо лучи.
Доказательство:
[math]\triangleright[/math]
Voronoi-not-lines.png
В случае, если все сайты лежат на одной прямой, каждая пара соседних сайтов порождает серединный перпендикуляр к отрезку, содержащему их, и, соответственно, к прямой, которая содержит все сайты. Так получаются [math]n - 1[/math] прямая, каждая из которых перпендикулярна прямой, содержащей сайты, а значит, эти прямые параллельны.

Рассмотрим теперь случай, когда сайты не лежат на одной прямой. Покажем, что рёбра — это отрезки или лучи, от противного. Предположим, что есть ребро [math]e[/math], являющееся прямой. Пусть оно — граница ячеек [math]\mathcal{V}(p_i)[/math] и [math]\mathcal{V}(p_j)[/math]. Пусть точка [math]p_k \in P[/math] не лежит на прямой [math]p_i p_j[/math] (по условию такая точка существует). Тогда серединный перпендикуляр к [math]p_j p_k[/math] не параллелен [math]e[/math], и, значит, он его пересекает. Но тогда та часть [math]e[/math], что лежит в [math]h(p_k, p_j)[/math], не может быть границей [math]\mathcal{V}(p_j)[/math], потому что она ближе к [math]p_k[/math], чем к [math]p_j[/math]. Пришли к противоречию.

Докажем теперь, что диаграмма связна. Предположим, что это не так. Тогда на её рёбрах найдутся две точки [math]s[/math] и [math]t[/math], между которыми нет пути по рёбрам диаграммы. Рассмотрим отрезок [math]st[/math]. Он пересекает некоторое количество ячеек диаграммы. Пусть он пересекает какую-то ячейку в точках [math]a[/math] и [math]b[/math]. От точки [math]a[/math] до точки [math]b[/math] можно добраться по рёбрам тогда и только тогда, когда ячейка связна. Раз пути из [math]s[/math] в [math]t[/math] нет, то какая-то из ячеек, пересекаемых отрезком [math]st[/math], несвязная. Это возможно, только если она представляет собой полосу, ограниченную двумя параллельными прямыми. Но в нашем случае в диаграмме не может быть прямых, пришли к противоречию.

Voronoi-connected.png
[math]\triangleleft[/math]

Размер структуры

Теорема:
Для [math]n \geqslant 3[/math] сайтов диаграмма Вороного содержит не больше [math]2n - 5[/math] вершин и [math] 3n - 6[/math] рёбер.
Доказательство:
[math]\triangleright[/math]
Voronoi-infinite-vertex.png
Для случая сайтов, лежащих на одной прямой, утверждение напрямую следует из вида диаграммы для этого случая, поэтому рассмотрим общий случай. По формуле Эйлера [math]v - e + f = 2[/math], где [math]v[/math] — число вершин, [math]e[/math] — число рёбер и [math]f[/math] — число граней связного планарного графа. Мы не можем сразу применить эту формулу к [math]Vor(P)[/math], потому что в этом графе есть полубесконечные рёбра. Поэтому добавим вершину [math]v_\infty[/math], и все полубесконечные рёбра мы превратим в рёбра, инцидентные ей. Таким образом мы увеличили число вершин на одну, а число рёбер не изменилось. Число граней равно [math]n[/math] по определению диаграммы Вороного. Тогда по формуле Эйлера получаем [math](v + 1) - e + n = 2[/math].

Сумма степеней всех вершин полученного графа равна [math]2e[/math], так как у каждого ребра есть ровно два конца (нет петель). Также из каждой вершины исходят как минимум три ребра. Отсюда получаем [math]2e \geqslant 3 (v + 1)[/math].

Домножим равенство на два и вычтем из него полученную нижнюю границу для [math]2 \cdot e[/math], в результате получим [math] v \leqslant 2n - 5[/math]. Далее подставим этот результат в равенство и получим [math]e \leqslant 3n - 6[/math], что и требовалось доказать.
[math]\triangleleft[/math]

Связь с триангуляцией Делоне

Определение:
Наибольшая пустая окружность точки [math]q[/math] по отношению к [math]P[/math] (largest empty circle of [math]q[/math] with respect to [math]P[/math], [math]C_P(q)[/math]) — наибольшая окружность с центром в [math]q[/math] такая, что во внутренности соответствующего ей круга не лежит ни одного сайта из [math]P[/math].


Лемма:
Точка [math]q[/math] — вершина диаграммы Вороного в том и только в том случае, когда [math]C_P(q)[/math] содержит три и более сайтов на своей границе.
Доказательство:
[math]\triangleright[/math]

Предположим, что [math]q[/math] существует, а [math]p_i, \ p_j, \ p_k[/math] — соответствующие точки. Так как внутри [math]C_P(q)[/math] нет других сайтов, а [math]q[/math] равноудалена от точек [math]p_i, \ p_j, \ p_k[/math], [math]q[/math] должна быть на границе [math]\mathcal{V}(p_i), \ \mathcal{V}(p_j), \ \mathcal{V}(p_k)[/math] одновременно, то есть вершиной диаграммы.

Докажем в другую сторону: каждая вершина [math]q[/math] диаграммы инцидентна минимум трём рёбрам, и, поэтому, как минимум трём ячейкам [math]\mathcal{V}(p_i), \ \mathcal{V}(p_j), \ \mathcal{V}(p_k)[/math]. Тогда [math]q[/math] лежит на равном расстоянии от [math]p_i, \ p_j, \ p_k[/math] и не может быть другого сайта ближе к [math]q[/math], так как иначе [math]\mathcal{V}(p_i), \ \mathcal{V}(p_j), \ \mathcal{V}(p_k)[/math] не сойдутся в [math]q[/math]. Поэтому можно построить окружность с центром в [math]q[/math] и [math]p_i, \ p_j, \ p_k[/math] на границе так, что внутри не будет других сайтов.
[math]\triangleleft[/math]
Лемма:
Серединный перпендикуляр к отрезку [math]p_i p_j[/math] образует ребро диаграммы Вороного в том и только в том случае, если на нём есть точка [math]q[/math] такая, что [math]C_P(q)[/math] содержит на своей границе только сайты [math]p_i, \ p_j[/math].
Доказательство:
[math]\triangleright[/math]
Voronoi-circles.png
Предположим, что [math]q[/math] существует. Тогда, так как [math]C_P(q)[/math] не содержит в себе сайтов и содержит [math]p_i, \ p_j[/math] на границе, [math] \rho(q, p_i) = \rho(q, p_j) \leqslant \rho(q, p_k), \ 1 \leqslant k \leqslant n[/math]. Отсюда выходит, что [math]q[/math] — вершина [math]Vor(P)[/math] или лежит на ребре диаграммы. Но по предыдущей лемме выходит, что [math]q[/math] не может быть вершиной диаграммы. Значит, она лежит на ребре, заданном серединным перпендикуляром к [math]p_i p_j[/math]. Докажем в другую сторону: пусть серединный перпендикуляр к [math]p_i p_j[/math] задаёт ребро диаграммы. Наибольшая пустая окружность любой точки [math]q[/math] на этом ребре должна содержать на границе [math]p_i[/math] и [math]p_j[/math] (так как [math]q[/math] равноудалена от [math]p_i[/math] и [math]p_j[/math]). Также эта окружность не должна содержать никаких других сайтов на границе, так как тогда она не является вершиной.
[math]\triangleleft[/math]
Теорема:
Если соединить все сайты, соответствующие смежным ячейкам диаграммы Вороного, получится триангуляция Делоне для этого множества точек.
Доказательство:
[math]\triangleright[/math]
Если ячейки, соответствующие сайтам [math]p_i, \ p_j[/math], смежны, то серединный перпендикуляр к отрезку [math]p_i p_j[/math] образует ребро диаграммы Вороного, то есть к нему применима предыдущая лемма и можно построить окружность с [math]p_i[/math] и [math]p_j[/math] на границе, внутри которой не будет других сайтов. Триангуляции Делоне принадлежат те и только те рёбра (с поправкой на точки, лежащие на одной окружности), на которых можно построить такую окружность, что внутри неё не будет лежать никаких точек. Тогда ребро [math]p_i p_j[/math] является ребром триангуляции Делоне. За счёт равносильности в обеих используемых леммах мы добавим все рёбра и не построим лишних.
[math]\triangleleft[/math]

Построение

Наивный алгоритм

Будем пересекать полуплоскости по свойству ячейки диаграммы. Необходимо для каждого сайта пересечь [math]n - 1[/math] плоскость, что суммарно делается за [math]O(n^2 \log n)[/math].

Инкрементальный алгоритм

Храним диаграмму в РСДС. Пусть у нас уже есть диаграмма для точек [math]p_1, p_2, ..., p_i[/math]. Добавим новый сайт [math]p_{i+1}[/math]. Сначала найдём сайт [math]p_j[/math], в ячейку которого попадает [math]p_{i+1}[/math], перебором. После этого строим новую ячейку: сначала проведём серединный перпендикуляр для [math]p_{i+1}p_j[/math], он пересечёт границу ячейки [math]\mathcal{V}(p_j)[/math] с ячейкой [math]\mathcal{V}(p_k)[/math]; на следующем шаге будем строить серединный перпендикуляр для [math]p_{i+1} p_k[/math] и так далее.

В процессе построения перпендикуляров необходимо обновлять РСДС. Каждый раз, когда новое полуребро [math]e[/math], порождаемое [math]p_{i+1}[/math] и [math]p_j[/math], пересекает существовавшее ранее полуребро [math]e'[/math], создаётся новая вершина [math]v[/math] и начинается новое полуребро [math]e+1[/math].

Обновление РСДС происходит следующим образом:

  • создаём вершину [math]v[/math] с полуребром [math]e[/math];
  • для полуребра [math]e[/math] в РСДС второй конец в вершине [math]v[/math], следующее полуребро — [math]e'[/math], инцидентные грани — слева [math]\mathcal{V}(i+1)[/math], справа — [math]\mathcal{V}(j)[/math];
  • добавляем в РСДС полуребро [math]e + 1[/math] с началом в [math]v[/math] и предыдущим полуребром [math]e[/math];
  • удаляем все полурёбра, лежащие между вершиной начала [math]e[/math] и вершиной конца [math]e[/math], по часовой стрелке;
  • обновляем полуребро, соответствующее грани для [math]\mathcal{V}(p_j)[/math] — им становится [math]e[/math].

Каждый шаг выполняется за [math]O(i)[/math], значит, суммарно диаграмма из [math]n[/math] сайтов с нуля создаётся за [math]O(n^2)[/math].

Локализация
Добавление первого ребра
Добавление третьего ребра
Обновление структуры при добавлении ребра

Алгоритм Форчуна

Построение производится при помощи заметающей прямой и парабол позади неё (параболы в данном случае - это множества точек, равноудалённых от вершины и прямой). Сама диаграмма "рисуется" местами соприкасания соседних парабол. Несмотря на то, что в теории движение прямой происходит непрерывно, сам алгоритм обрабатывает только крайние случаи, когда происходят события. Рассматривается 2 типа событий - появление новой параболы, когда заметающая прямая касается вершины, и схлопывание параболы - когда две соседние параболы её полностью накрывают. Всего событий [math]O(n)[/math] ([math]n[/math] - число вершин). Для каждого события вычисляется его время (позиция заметающей прямой), события кладутся в очередь с приоритетом (отсюда [math]O(\log n)[/math] по времени) и обрабатываются, пока очередь непуста. При обработке событий также записываются пары взаимодействующих вершин (у которых сайты имеют общую границу), это и является результатом работы алгоритма.

Сложность работы алгоритма - [math]O(n \log n)[/math] по времени и [math]O(n)[/math] по памяти.

Более подробно:

Алгоритм Чана

Вершины проецируются из двумерной плоскости на поверхность параболоида ([math]x, y[/math] остаются те же, добавляется [math]z = x^2 + y^2[/math]). Далее по ним строится нижняя выпуклая оболочка. Поскольку параболоид выпуклый, никакие вершины не будут удалены. На выходе получаются рёбра между вершинами, которые соответствуют триангуляции Делоне. Сложность работы - [math]O(n \log n)[/math].

Диаграмма k-го порядка

Определение:
Ячейка Вороного [math]k[/math]-го порядка ([math]\mathcal{V}_k(p_1, p_2, ..., p_k)[/math]) — множество точек, имеющих в качестве ближайших [math]k[/math] соседей множество сайтов [math]p_1, p_2, ..., p_k[/math].


Чтобы построить диаграмму [math]k[/math]-го порядка, возьмём диаграмму [math]k - 1[/math]-го порядка. Каждая ячейка построена для некоторого набора [math]k-1[/math] сайтов. Обозначим множество этих сайтов за [math]S[/math]. Пересечём каждую из этих ячеек с ячейками диаграммы первого порядка, построенной на множестве сайтов [math]P \setminus S[/math]. Когда мы пересекаем ячейку [math]k-1[/math]-го порядка для точек [math]S[/math] с ячейкой первого порядка для точки [math]p_i[/math], получаем ячейку для множества [math]S \cup \{p_i\}[/math]. После пересечения ячеек необходимо объединить те, которые отвечают за одинаковый набор сайтов (это могут быть только соседние по ребру ячейки).

Итого совершаем [math]k[/math] шагов, на каждом строим [math]O(n)[/math] диграмм Вороного за время [math]O(n^3)[/math], пересекаем [math]O(n)[/math] ячеек с [math]O(n)[/math] ячейками за [math]O(n)[/math] времени, а потом объединяем ячейки за [math]O(n)[/math] (линейное количество соседних рёбер ячейки, а объединение происходит за [math]O(1)[/math] за счёт структуры РСДС). Итого [math]O(k \cdot n^3)[/math].

Диаграмма первого порядка
Диаграмма второго порядка
Диаграмма третьего порядка
Диаграмма [math]n - 1[/math]-го порядка (она же farthest-point диаграмма) для данного набора сайтов

Farthest-point диаграмма

Определение:
Диаграмма [math]n - 1[/math]-го порядка является farthest-point диаграммой, т.е. в каждой её ячейке все точки являются наиболее удалёнными от какого-то сайта.


Свойства

Лемма:
Для любой точки [math]q[/math] плоскости самый удалённый от неё сайт из [math]P[/math] должен лежать на выпуклой оболочке [math]P[/math].
Доказательство:
[math]\triangleright[/math]
Voronoi-farthest-inside.png
Сайт, не находящийся на выпуклой оболочке, лежит внутри неё по свойствам выпуклой оболочки. Пусть самый удалённый от точки [math]q[/math] сайт [math]p_i[/math] не лежит на выпуклой оболочке (т.е. лежит внутри неё). Проведём луч [math]q p_i[/math]. Он пересечёт ребро выпуклой оболочки [math]p_j p_k[/math]. Получатся два смежных угла, рассмотрим тот, который оказался прямым или тупым. Тогда в полученном треугольнике [math]\rho(q, p_j) \gt \rho(q, p_i)[/math], так как напротив большего угла лежит большая сторона. Пришли к противоречию.
[math]\triangleleft[/math]
Лемма:
Сайт, который лежит внутри выпуклой оболочки сайтов, не может иметь ячейку в farthest-point диаграмме.
Доказательство:
[math]\triangleright[/math]
Пусть это не так и сайт [math]p[/math] лежит внутри выпуклой оболочки и имеет ячейку в farthest-point диаграмме. Тогда внутри неё есть точка [math]q[/math]. Но по предыдущей лемме самый удалённый для [math]q[/math] сайт лежит на выпуклой оболочке, а значит, сайт [math]p[/math] не может быть самым удалённым для [math]q[/math]. Пришли к противоречию.
[math]\triangleleft[/math]
Лемма:
Каждый сайт, который является вершиной выпуклой оболочки сайтов, имеет ячейку в farthest-point диаграмме.
Доказательство:
[math]\triangleright[/math]

Докажем по индукции.

База индукции: для двух сайтов они оба являются вершинами выпуклой оболочки и оба имеют ячейку в farthest-point диаграмме (дальняя от сайта полуплоскость).

Переход: добавим сайт [math]p[/math] так, что он станет новой вершиной выпуклой оболочки. Пусть он не имеет ячейку в farthest-point диаграмме, то есть уже имеющаяся перед его добавлением диаграмма не меняется. Для построения farthest-point диаграммы проводятся серединные перпендикуляры между всеми парами сайтов, и полученные полуплоскости пересекаются; раз новой ячейки не добавилось, то серединные перпендикуляры между [math]p[/math] и остальными сайтами совпали с уже имеющимися перпендикулярами. Это возможно, только если [math]p[/math] совпал с другим сайтом. Пришли к противоречию.
[math]\triangleleft[/math]
Утверждение:
Сайт имеет ячейку в farthest-point диаграмме тогда и только тогда, когда он является вершиной выпуклой оболочки всех сайтов.
[math]\triangleright[/math]
Непосредственно следует из двух предыдущих лемм.
[math]\triangleleft[/math]
Утверждение:
Все ячейки в farthest-point диаграмме неограничены.
[math]\triangleright[/math]
Voronoi-farthest-unbounded.png
Пусть [math]p_i[/math] — сайт на выпуклой оболочке сайтов, а [math]q[/math] — точка, для которой он является наиболее удалённым. Тогда для всех точек на луче, лежащем на [math]p_i q[/math], начинающемся в [math]q[/math] и не проходящим через [math]p_i[/math], сайт [math]p_i[/math] будет наиболее удалённым среди остальных сайтов. Значит, ячейка сайта [math]p_i[/math] в farthest-point диаграмме включает в себя этот луч, а значит, неограничена.
[math]\triangleleft[/math]

Алгоритм

Чтобы найти farthest-point диаграмму, сначала найдём выпуклую оболочку всех сайтов. Обозначим сайты, её образующие, через [math]p_1, p_2, ..., p_m[/math]. Запомним порядки обхода для каждой вершины выпуклой оболочки по часовой стрелке ([math]cw(p_i)[/math]) и против часовой ([math]ccw(p_i)[/math]) и сделаем случайную перестановку точек. Далее удаляем из выпуклой оболочки все точки, кроме первых трёх (запоминая при этом их соседей в оболочке на момент удаления). После этого строим farthest-point диаграмму для первых трёх точек (пересекая полуплоскости) и последовательно добавляем остальные (удалённые) в порядке, обратном порядку удаления.

Построение очередной ячейки farthest-point диаграммы

Для точки [math]p_i[/math] ячейка встанет «между» ячейками, соответствующими [math]cw(p_i)[/math] и [math]ccw(p_i)[/math]. Перед добавлением [math]p_i[/math] [math]cw(p_i)[/math] и [math]ccw(p_i)[/math] — соседи, поэтому между ними построен серединный перпендикуляр. Серединный перпендикуляр к [math]p_i ccw(p_i)[/math] даст новое ребро, которое лежит в farthest-point ячейке [math]ccw(p_i)[/math] и является частью границы ячейки [math] p_i[/math]. Обойдём ячейку [math]ccw(p_i)[/math] по часовой стрелке, чтоб понять, какое ребро пересечёт перпендикуляр. С другой стороны этого ребра лежит ячейка какой-то точки [math]p_j[/math], и серединный перпендикуляр [math]p_i p_j[/math] тоже даст ребро ячейке [math]p_i[/math]. Аналогично совершим обход и так далее. Последний серединный перпендикуляр будет построен для [math]p_i cw(p_i)[/math]. После этого удаляем рёбра, которые лежат внутри новой ячейки.

См. также

Источники