Изменения
Замена темина
{{Определение
|definition=
Будем называть лестницу <tex>D</tex> полностью соотносимой множеству '''полной''' относительно множества отрезков <tex>S</tex>, если каждый отрезок из <tex>S</tex> либо не пересекает полосу <tex>\langle a, b \rangle</tex>, либо пересекает хотя бы одну из ступенек из множества <tex>D</tex>.
}}
|id=lemma1
|statement=
Пусть лестница <tex>D</tex> полностью соотносима множеству полна относительно множества отрезков <tex>S</tex>, где <tex>S</tex> состоит из отрезков, пересекающих полосу <tex>\langle a, b \rangle</tex>, тогда <tex>|S| \le Ends_{a, b}(S) + |Int(D, S)|</tex>,<br>
где <tex>Ends_{a, b}(S)</tex> это число вершин отрезков из <tex>S</tex>, находящихся в пределах полосы <tex>\langle a, b \rangle</tex>.
}}
===Split===
Функция <tex>Split</tex> разделяет входное множество отрезков <tex>L</tex>, пересекающих некоторую полосу <tex>\langle a, b \rangle</tex>, на подмножества <tex>Q</tex> и <tex>L'</tex> так, что лестница <tex>(Q, \langle a, b \rangle)</tex> полностью соотносима множеству полна относительно множества отрезков <tex>L'</tex>.
Пусть <tex>L = (s_1 ,..., s_k)</tex>, где <tex>s_i <_a s_{i+1}</tex>
Предположим, что все отрезки лежат в полосе <tex>\langle a, b\rangle</tex>. Таким образом в самом начале у нас есть пара <tex>(S, \langle a, b\rangle)</tex>.
Что же дальше происходит: множество <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>\}</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>;
