Изменения

Большинство из шагов в приведенном выше описании принимать только константное время. Есть случаи на которые потребуется дополнительное время, О(M), где M­число ребер, точки событий. Это означает, что обновление <tex>D</tex> не увеличивает время работы алгоритма заметащей прямой асимптотически. Любое пересечение, которое мы находим является вершиной наложения. Из этого следует, что вершина record и <tex>half-edge</tex> record doubly­ connected edge list для <tex>O(S1, S2)</tex> можно вычислить в за <tex>O(Nn\ *\ log Nn\ +\ k\ *\ log\ n)</tex> время, где <tex>n</tex> обозначает сумму сложностей <tex>S1</tex> и <tex>S2</tex>, а k является сложностью наложения.

|proof= Рассмотрим цикл <tex>C</tex>, который ограничивает дыру в <tex>face</tex> <tex>f</tex>. Поскольку <tex>f</tex> локально лежит левее самой левой вершины из <tex>C</tex>, то <tex>C</tex> должен быть соединен с другим циклом, который тоже ограничивает <tex>f</tex>. отсюда следует, что циклы есть компонента связности в графе, описывающая один и тот-же <tex>face</tex>. Для того, что бы закончить доказательство, покажем, что каждый цикл ограничивающий дыру в <tex>f</tex> есть в той же компоненте связности, что и внешняя граница <tex>f</tex>. Предположим, что есть цикл, для которого это не так. Пусть <tex>C</tex> — самый левый такой цикл, то есть тот, чья самая левая вершина самая левая (шляпа). По определению есть ребро между <tex>C</tex> и неким <tex>C'</tex>, который лежит слева от самой левой вершины <tex>C</tex>. Следовательно <tex>C</tex> в той же компоненте связности, что и <tex>C'</tex>, который не в той же компоненте, что внешняя граница <tex>f</tex>. Противоречие.