Изменения
→Перевод
Что же дальше происходит: множество <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>\[1, 2N\]</tex>. Пусть <tex>p_i{</tex> и <tex>s(i)</tex> будут координатами вершин <tex>i</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>
<tex>\{</tex>
'''if''' <tex>b - a = 1</tex> '''then'''
<tex>\{</tex>
<tex>L \leftarrow sort </tex> отсортируем <tex>S_v by </tex> по отношению <tex><_b</tex>;
<tex>SearchInStrip_{a, b}(L_v, R_v)</tex>;
<tex>\}</tex>
==Примечания==
