Изменения

Что же дальше происходит: множество <tex>S</tex> ''распадается'' в подмножества <tex>Q</tex> и <tex>S'</tex>, после чего лестница <tex>D = (Q, \langle a, b \rangle)</tex> становится полностью соотносимой множеству <tex>S'</tex>. Необходимо найти пересечения отрезков из <tex>D</tex> и <tex>S'</tex>, затем, все пересечения в <tex>S'</tex>. Чтобы найти пересечения отрезков в <tex>S'</tex>, мы ''режем'' полосу <tex>\langle a, b \rangle</tex> и множество <tex>S'</tex> по вертикале <tex>x = c</tex> на полосы <tex>\langle a, c \rangle</tex>, <tex>\langle c, b \rangle</tex> и множества <tex>S'_{ls}</tex>, <tex>S'_{rs}</tex> соответственно, где <tex>c</tex> является медианой вершин отрезков между <tex>a</tex> и <tex>b</tex>. Затем мы рекурсивно вызываем функцию к парам <tex>(S'_{ls}, \langle a, c \rangle)</tex> и <tex>(S'_{rs}, \langle c, b \rangle)</tex>. Ключевым является тот факт, что согласно [[#lemma1|лемме]] <tex>|S'| \le Ends_{a, b}(S') + |Int(D, S')|</tex>, таким образом, число дополнительных отрезков, появляющихся после ''разрезаний'' пропорционально числу найденных пересечений.

Давайте разберемся с алгоритмом более подробно:

Заметим, что нахождение <tex>Int(D_v, R_{rs(v)})</tex> надо делать аккуратно, так как множества <tex>R_{rs(v)}</tex> и <tex>L_{ls(v)}</tex> могут иметь одни и те же отрезки (которые '''пересекают''' <tex>\langle a, b \rangle</tex>). Мы нашли их пересечения с <tex>D_v</tex> при поиске <tex>Int(D_v, L_{ls(v)})</tex>, и не должны вывести эти пересечения снова.

Для начала рассчитаем место, необходимое для выполнения алгоритма. Алгоритм использует рекурсивную функцию <tex>TreeSearch</tex>. Последовательность вызовов функции может занять память. Эта последовательность может быть представлена как путь корня рекурсивного дерева, до узла. Соответствующий вызов этого узла занимает <tex>O(N)</tex> памяти, каждый его "предок" занимает <tex>O(|I_v| + |Q_v|)</tex> памяти, а остальные структуры используют <tex>O(N)</tex>. Очевидно, что любой путь <tex>pt</tex> от корня рекурсивного дерева до какого-то узла <tex>\sum_{v \in pt}(|I_v + |Q_v|) = O(N)(|I_v| \le b_v - a_v \le \lceil (b_{ft(v)} - a_{ft(v)})/2 \rceil)</tex>.

В итоге для работы алгоритма требуется <tex>O(N)</tex> памяти.

{{Лемма