Изменения
→Основной алгоритм
Что же дальше происходит: множество <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>L \leftarrow</tex> отсортируем <tex>S_v</tex> по отношению <tex><_b</tex>;
<tex>SearchInStrip_{a, b}(L_v, R_v)</tex>;
'''return''';
<tex>\}</tex>
Разделим <tex>S_v</tex> на <tex>Q_v</tex> и <tex>S_v'</tex> так, что лестница
<tex>D_v := \leftarrow (Q_v, \langle a, b \rangle)</tex> будет полностью соотносима множеству <tex>S_v'</tex>;
Найдем <tex>Int(D_v, S_v')</tex>;
<tex>c := \leftarrow \lfloor (a + b)/2 \rfloor</tex>;
Разделим отрезки из <tex>S_v'</tex> на пересекающих
полосу <tex>\langle a, c \rangle</tex> <tex>S_{ls}(v)</tex> и
Чтобы решить эту проблему, представим <tex>S_v</tex> как объединение трех множеств:
множества <tex>L_v</tex> упорядоченного по отношению <tex><_a</tex>, неупорядоченного множества <tex>I_v</tex>, и множества <tex>R_v</tex> упорядоченного по отношению <tex><_b</tex>. Расположим отрезки из <tex>S_v</tex>, пересекающие границу <tex>x = a</tex> во множество <tex>L_v</tex>, отрезки пересекающие <tex>x = b</tex> во множество <tex>R_v</tex>, и внутренние отрезки во множество <tex>I_v</tex> (пример на рисунке справа).
Теперь мы можем вызвать функцию <tex>Split</tex> для множества <tex>L_v</tex> и построить <tex>Q_v</tex> за <tex>O(|L_v|) = O(|S_v|)</tex> времени. Но мы натыкаемся на новую проблему: передавая множества <tex>L_v</tex>, <tex>I_v</tex> и <tex>R_v</tex>, необходимо найти соответствующие множества сыновей узла <tex>v</tex>.
Неупорядоченные множества <tex>I_{ls(v)}</tex> и <tex>I_{rs(v)}</tex> строятся легко. Множество <tex>L_{ls(v)}</tex> будет найдено вызовом функции <tex>Split_{a, b}(L_v, Q_v, L_{ls(v)})</tex> для третьего шага функции <tex>TreeSearch</tex>. Множество <tex>L_{rs(v)}</tex> получается из <tex>R_{ls(v)}</tex> за линейное время вставкой (если <tex>p_c</tex> левый конец отрезка) или удалением (если <tex>p_c</tex> правый конец отрезка) отрезка <tex>s(c)</tex>. Но как получить <tex>R_{ls(v)}</tex> из <tex>L_v</tex>, <tex>R_v</tex> и <tex>I_v</tex> без сортировки?
Для листьев мы сделаем проверку вначале, и получим <tex>R_v</tex> из <tex>L_v</tex>. Пусть <tex>L_v</tex> и <tex>I_v</tex> известны, и все сыновья узла <tex>v</tex> - листья. Для начала запустим функцию <tex>Split(L_v, Q_v, L_{ls(v)})</tex> и найдем <tex>Q_v</tex> и <tex>L_{ls(v)}</tex>. Теперь мы должны найти <tex>Int(D_s, S_v') = Int(D_v, L_{ls(v)}) \cup Int(D_v, I_v) \cup Int(D_v, R_{rs(v)})</tex>, но мы не знаем <tex>R_{rs(v)}</tex>, и соответственно можем найти только <tex>Int(D_v, L_{ls(v)}) \cup Int(D_v, I_v)</tex>. Применим <tex>SearchInStrip</tex> к множеству <tex>L_{ls(v)}</tex> и получим <tex>R_{ls(v)}</tex>. Множество <tex>L_{rs(v)}</tex> получается из <tex>R_{ls(v)}</tex> вставкой или удалением отрезка <tex>s(c)</tex>. Применим <tex>SearchInStrip</tex> к <tex>L_{rs(v)}</tex> и найдем <tex>R_{rs(v)}</tex>. Теперь можем продолжить вычисление <tex>Int(D_v, R_{rs(v)})</tex> и получим <tex>R_v</tex> слиянием <tex>Q_v</tex> и <tex>R_{rs(v)}</tex>.
Конечная функция будет выглядеть так:
<tex>IntersectingPairs(S_0)</tex>
<tex>\{</tex>
Отсортируем <tex>2N</tex> концов отрезков по абсциссе
и найдем <tex>p_i</tex>, <tex>s(i)</tex> где <tex>i = 1, ..., 2N</tex>;
<tex>L_r \leftarrow (s(1))</tex>; <tex>I_r \leftarrow S_0 \setminus (\{s(1)\} \cup \{s(2N)\})</tex>;
<tex>TreeSearch(L_r, I_r, 1, 2N, R_r)</tex>;
<tex>\}</tex>
<tex>TreeSearch(L_v, I_v, a, b, R_v)</tex>
<tex>\{</tex>
'''if''' <tex>b - a = 1</tex> '''then'''
<tex>\{</tex>
<tex>SearchInStrip_{a, b}(L_v, R_v)</tex>;
'''return''';
<tex>\}</tex>
<tex>Split_{a, b}(L_v, Q_v, L_{ls(v)})</tex>;
<tex>D_v \leftarrow (Q_v, \langle a, b \rangle)</tex>;
Найдем <tex>Int(D_v, L_{ls(v)})</tex>;
<tex>c \leftarrow \lfloor (a + b) / 2 \rfloor</tex>;
Разделяем отрезки из <tex>I_v</tex>
внутренние для полосы <tex>\langle a, c \rangle</tex> во множество <tex>I_{ls(v)}</tex>
внутренние для полосы <tex>\langle c, b \rangle</tex> во множество <tex>I_{rs(v)}</tex>
<tex>TreeSearch(L_{ls(v)}, I_{ls(v)}, a, c, R_{ls(v)})</tex>;
'''if''' <tex>p_c</tex> левый конец отрезка <tex>s(c)</tex> '''then'''
<tex>L_{rs(v)} \leftarrow</tex> вставить <tex>s(c)</tex> в <tex>R_{ls(v)}</tex>
'''else'''
<tex>L_{rs(v)} \leftarrow</tex> удалить <tex>s(c)</tex> из <tex>R_{ls(v)}</tex>
<tex>TreeSearch(L_{rs(v)}, I_{rs(v)}, c, b, R_{rs(v)})</tex>;
Найдем <tex>Int(D_v, R_{rs(v)})</tex>;
'''for''' <tex>s \in I_v</tex> '''do'''
Найдем <tex>Loc(D_v, s)</tex> используя двоичный поиск;
Найдем <tex>Int(D_v, I_v)</tex> используя значения, полученные шагом выше;
<tex>R_v \leftarrow Merge_b(Q_v, R_{rs(v)})</tex>;
<tex>\}</tex>
==Примечания==
