64
правки
Изменения
Нет описания правки
'''Сайт''' (''site'') {{---}} общее название для точки <tex>p</tex> или замкнутого отрезка <tex>t</tex>.
<tex>t^\circ</tex> {{---}} внутренность внутренняя часть отрезка. Внутренность точки {{---}} пустое множество.
Два замкнутых пересекающихся сайта '''слабо пересекаются''' (''weakly intersect''), если точка их пересечения не принадлежит их внутренностям, то есть они касаются концами.
Пусть сайт <tex>S</tex> {{---}} это точка <tex>p</tex>.
{|border="0" width="100%"|{{Теорема
|statement=
Пусть <tex>\Sigma</tex> {{---}} множество слабо пересекающихся сайтов, <tex>p</tex> {{---}} точка, <tex>p \notin \Sigma</tex>. Тогда <tex>R_\Sigma(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 = \varnothing \Rightarrow P \cap V_1^\circ(\Sigma) = \varnothing \Rightarrow P \subseteq VintV(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(qs, \Sigma)</tex>. Значит, точки пересечения этих окрестностей с дополнением <tex>C</tex> лежат в <tex>V(qs, \Sigma \cup p)</tex> и могут быть соединены путём <tex>L \subseteq V(qs, \Sigma \cup \{p\}) \subseteq V(qs, \Sigma)</tex>. Следовательно, цикл <tex>P \circ L</tex> полностью содержится в <tex>V(qs, \Sigma)</tex> и содержит <tex>\varepsilon_1</tex> и или <tex>\varepsilon_2</tex> в своей внутренностивнутренней части. Это противоречиепротиворечит тому, что <tex>V(s, \Sigma)</tex> {{---}} односвязное множество, следовательно <tex>k = 1</tex>.
}}
|[[Файл:path.png|250px|thumb|right]]
|}
Таким образом, для нахождения области конфликтов, можно найти одно конфликтующее ребро, а затем, при помощи DFS, найти все остальные.
