418
правок
Изменения
→Инкрементальный алгоритм
Обновление РСДС происходит следующим образом:
* создаём вершину <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>v</tex> с ребром <tex>e</tex>.
Каждый шаг выполняется за <tex>O(i)</tex>, значит, суммарно диаграмма из <tex>n</tex> сайтов с нуля создаётся за <tex>O(n^2)</tex>.
