Изменения

Далее, по ходу алгоритма мы обрабатываем каждое событие. Обработка включает в себя удаление события (<tex>O(nlog\log{n})</tex>), вызов функции findIntersection до двух раз, что может вызвать вставку новых событий <tex>O(n\log{n})</tex>. Также при обработке события <tex>p</tex> мы <tex>m(p) = \vert L(p) \cup C(p) \cup \U(p) \vert</tex> раз выполняем операции вставки, удаления, поиска над <tex>T</tex>. Каждая из этих операций требует <tex>O(\log{n})</tex> времени. Пусть <tex>m = \sum_{p} {m(p)}</tex>. Тогда время работы алгоритма {{---}} <tex>O(m\log{n})</tex>

Покажем, что <tex>m = O(n + I)</tex>, где <tex>I</tex> {{---}} количество пересечений.Для этого рассмотрим планарный граф, вершинами которого являются концы отрезков, а также их точки пересечения, а ребрами {{---}} части отрезков, их соединяющие. Рассмотрим событие <tex>p</tex>. Ему соответствует вершина графа со степенью <tex>O(m(p))</tex>, следовательно <tex>m = O(\sum_{p} {deg(p)}) = O(E) = O(V) = O(2n + I)</tex>, где <tex>deg(p)</tex> {{---}} степень <tex>p</tex>, <tex>E</tex> {{---}} число ребер в графе, <tex>V</tex> {{---}} число вершин. (Предпоследний переход следует из формулы Эйлера.)