Изменения

Что же дальше происходит: множество <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> соответственно, где c является медианой вершин отрезков, между <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>TreeSearch</tex>. Мы соединяем каждый вызов функции с узлом некоего двоичного дерева (далее ''рекурсивное дерево''). Мы отмечаем все значения, множества и параметры вызова соответствующим узлом. В результате, мы проанализируем наш алгоритм рекурсивного дерева. Обозначим множество всех вершин рекурсивного дерева за <tex>RT</tex>, а множество внутренних вершин за <tex>V</tex>. (WAT??)

<tex>IntersectingPairs(S_v, a, b):</tex>

<tex>TreeSearch(S_r, a, b):</tex>

'''if''' <tex>b - a = 1</tex> '''then'''

<tex>\{</tex>

<tex>SearchInStrip_{a, b}(L_v, R_v)</tex>;

<tex>\}</tex>

==Примечания==