64
правки
Изменения
м
Нет описания правки
Для начала докажем, что ячейки связны. Пусть это не так и у ячейки <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>. Опять противоречие.
}}
Пусть сайт <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_V(S, \Sigma(p\cup \{S\})</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>, то есть, можно опустить шаг поиска ближайшего соседа. Остаётся найти всю область конфликтов, как и в случае с точкой.
