Изменения

Пусть <tex>\Sigma</tex> {{---}} множество слабо пересекающихся сайтов, <tex>ps</tex> {{---}} точкасайт, <tex>p s \notin \Sigma</tex>. Тогда <tex>R_\Sigma(ps)</tex> {{---}} связная кривая, содержащая более одной точкисвязное непустое множество.

Пусть <tex>C = V(ps, \Sigma \cup \{ps\})</tex>, <tex>R_\Sigma(ps) = \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 ps)</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(sq, \Sigma)</tex> для некоторого <tex>s q \in \Sigma</tex>. <tex>x, y \in P \Rightarrow</tex> все достаточно малые окрестности <tex>U(x)</tex>, <tex>U(y)</tex> полностью содержатся в <tex>V(sq, \Sigma)</tex>. Значит, точки пересечения этих окрестностей с дополнением <tex>C</tex> лежат в <tex>V(sq, \Sigma \cup ps)</tex> и могут быть соединены путём <tex>L \subseteq V(sq, \Sigma \cup \{ps\}) \subseteq V(sq, \Sigma)</tex>. Следовательно, цикл <tex>P \circ L</tex> полностью содержится в <tex>V(sq, \Sigma)</tex> и содержит <tex>\varepsilon_1</tex> или <tex>\varepsilon_2</tex> в своей внутренней части. Это противоречит тому, что <tex>V(sq, \Sigma)</tex> {{---}} односвязное множество, следовательно <tex>k = 1</tex>.

Пусть сайт <tex>S</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>R_\Sigma(p)</tex>. Если же <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>, то есть, можно опустить шаг поиска ближайшего соседа. Остаётся найти всю область конфликтов, как и в случае с точкой.