418
правок
Изменения
→Инкрементальный алгоритм
Храним диаграмму в [[ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых|РСДС]]. Пусть у нас уже есть диаграмма для точек <tex>p_1, p_2, ..., p_i</tex>. Добавим новый сайт <tex>p_{i+1}</tex>. Сначала [[Локализация в ППЛГ методом полос (персистентные деревья)|найдём]] сайт <tex>p_j</tex>, в ячейку которого попадает <tex>p_{i+1}</tex>. После этого строим новую ячейку: сначала проведём серединный перпендикуляр для <tex>p_{i+1}p_j</tex>, он пересечёт границу ячейки <tex>\mathcal{V}(p_j)</tex> с ячейкой <tex>\mathcal{V}(p_k)</tex>; на следующем шаге будем строить серединный перпендикуляр для <tex>p_{i+1} p_k</tex> и так далее.
В процессе построения перпендикуляров необходимо обновлять РСДС. Каждый раз, когда новое ребро полуребро <tex>e</tex>, порождаемое <tex>p_{i+1}</tex> и <tex>p_j</tex>, пересекает существовавшее ранее ребро полуребро <tex>e'</tex>, создаётся новая вершина <tex>v</tex> и начинается новое ребро полуребро <tex>e+1</tex>.
Обновление РСДС происходит следующим образом:
* создаём вершину <tex>v</tex> с ребром полуребром <tex>e</tex>;* для ребра полуребра <tex>e</tex> в РСДС второй конец в вершине <tex>v</tex>, следующее ребро полуребро — <tex>e'</tex>, инцидентные грани — слева <tex>\mathcal{V}(i+1)</tex>, справа — <tex>\mathcal{V}(j)</tex>;* добавляем в РСДС ребро полуребро <tex>e + 1</tex> с началом в <tex>v</tex> и предыдущим ребром полуребром <tex>e</tex>;
* удаляем все рёбра, лежащие между вершиной начала <tex>e</tex> и вершиной конца <tex>e</tex>, по часовой стрелке;
* обновляем реброполуребро, соответствующее грани для <tex>\mathcal{V}(p_j)</tex> — им становится <tex>e</tex>.
Каждый шаг выполняется за <tex>O(i)</tex>, значит, суммарно диаграмма из <tex>n</tex> сайтов с нуля создаётся за <tex>O(n^2)</tex>.
