64
правки
Изменения
Нет описания правки
Расстояние от точки <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>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'') {{---}} связное множество точек, принадлежащих пересечению ровно двух ячеек Вороного.
'''4'''. Обновить локализационную структуру.
{{Лемма
|statement=
<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>. Опять противоречие.
}}
{|border="0" width="100%"
