Изменения

Пусть <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>. Ячейки Вороного односвязны.

'''Ребро Вороного''' (''Voronoi edge'') {{---}} непрерывное связное множество точек, которые принадлежат принадлежащих пересечению ровно двух ячеек Вороного.

Рассмотрим <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>\Sigma</tex>. Рассмотрим процедуру вставки нового сайта <tex>S</tex>. Алгоритм состоит из четырёх шагов: '''1'''. Найти первый конфликт сайта <tex>S</tex> с каркасом <tex>V_1(\Sigma)</tex>. '''2'''. Найти всю область конфликтов сайта <tex>S</tex> c каркасом <tex>V_1(\Sigma)</tex>. '''3'''. Построить диаграмму Вороного для <tex>\Sigma \cup \{S\} </tex>. '''4'''. Обновить локализационную структуру.  Пусть сайт <tex>S</tex> {{---}} это точка <tex>p</tex>. {{Теорема|statement=Пусть <tex>\Sigma</tex> {{---}} множество слабо пересекающихся сайтов, <tex>p</tex> {{---}} точка, <tex>p \notin \Sigma</tex>. Тогда <tex>\partial R_\Sigma(p)</tex> {{---}} связная кривая, содержащая более одной точки.|proof=Пусть <tex>C = V(p, \Sigma \cup \{p\})</tex>, <tex>R_\Sigma(p) = \varepsilon</tex>.  Заметим, что <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 p)</tex> не было бы односвязным. Пусть <tex>\varepsilon_1, \varepsilon_2, ... , \varepsilon_k</tex> {{---}} связные компоненты <tex>\varepsilon</tex> для некоторого <tex>k</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 = \emptyset \Rightarrow P \cap V_1^\circ(\Sigma) = \emptyset \Rightarrow P \subseteq V(s, \Sigma)</tex> для некоторого <tex>s \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 p)</tex> и могут быть соединены путём <tex>L \subseteq V(q, \Sigma \cup \{p\}) \subseteq V(q, \Sigma)</tex>. Следовательно, цикл <tex>P \circ L</tex> полностью содержится в <tex>V(q, \Sigma)</tex> и содержит <tex>\varepsilon_1</tex> и <tex>\varepsilon_2</tex> в своей внутренности. Это противоречие, следовательно <tex>k = 1</tex>.}}Таким образом, для нахождения области конфликтов, можно найти одно конфликтующее ребро, а затем, при помощи DFS, найти все остальные. Первый шаг алгоритма начинается с поиска ближайшего соседа <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>R_\Sigma(p)</tex>.