Изменения
Нет описания правки
|definition=
Будем говорить, что отрезок <tex>s</tex>, с вершинами в точках с абсциссами <tex>l</tex> и <tex>r</tex> :
- '''содержитохватывает'''(span) полосу <tex>\langle a, b \rangle</tex>, если <tex>l \le a \le b \le r</tex>; <br>
- '''внутренний'''(inner) для полосы <tex>\langle a, b \rangle</tex>, если <tex>a < l < r < b</tex>; <br>
- '''пересекает'''(cross) полосу <tex>\langle a, b \rangle</tex> в других случаях.
|definition=
''Лестница'' <tex>D</tex> — это пара <tex>(Q, \langle a, b \rangle)</tex>, в которой отрезки из множества <tex>Q</tex> удовлетворяют следующим условиям :
− любой отрезок из <tex>Q</tex> содержит охватывает полосу <tex>\langle a, b \rangle</tex>; <br>
− нет пересечений отрезков внутри лестницы; <br>
− <tex>Q</tex> упорядочена по отношению <tex><_a</tex>.
{{Определение
|definition=
Будем называть лестницу <tex>D</tex> '''полной''' относительно множества отрезков <tex>S</tex>, если каждый отрезок из <tex>S</tex> либо не содержит охватывает полосу <tex>\langle a, b \rangle</tex>, либо пересекает хотя бы одну из ступенек из множества <tex>D</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>
'''if''' отрезок <tex>S_j</tex> не пересекает
последний отрезок из <tex>Q</tex> внутри полосы <tex>\langle a, b \rangle</tex>
и при этом содержит охватывает её '''then'''
добавить <tex>s_j</tex> в конец <tex>Q;</tex>
'''else'''
