189
правок
Изменения
add picture
}}
{{Определение|definition=Два отрезка <tex>s_1</tex> и <tex>s_2</tex> называются ''пересекающимися внутри '' полосы <tex>\langle a, b \rangle</tex>, если их точка пересечения лежит в пределах этой полосы. <br>
Для двух множеств отрезков <tex>S</tex> и <tex>S'</tex> определим множество <tex>Int(S, S')</tex> как <tex>\{ {s, s'} | (s \in S, s' \in S') \& (s \ intersect \ s') \}</tex>.
}}
[[Файл:Balaban_pic_1.png|350px|thumb|right|<tex>D = ((s_1, s_2, s_3), \langle a, b \rangle)</tex>, <tex>Loc(D, s_4) = 0</tex>, <tex>Loc(D, s_5) = 2</tex> или <tex>3</tex>, <tex>Int(D, \{s_4,\ s_5\}) = \{\{s_3,\ s_5\}\}</tex>]]
Обозначения <tex>Int_{a, b}(S)</tex> и <tex>Int_{a, b}(S, S')</tex> будут использоваться для описания подмножеств <tex>Int(S)</tex> и <tex>Int(S, S')</tex>, состоящих из пересекающихся пар отрезков в пределах полосы <tex>\langle a, b \rangle</tex>. Далее скобки <tex>\{\}</tex> используются для определения неупорядоченных наборов, а скобки <tex>()</tex> используются для определения упорядоченных множеств.
{{Определение
|neat=neat
|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>p</tex> отрезка <tex>s</tex> лежит между ступеньками <tex>i</tex> и <tex>i + 1</tex>, тогда число <tex>i</tex> называется ''местоположением'' <tex>s</tex> на лестнице <tex>D</tex> и обозначается как <tex>Loc(D, s)</tex>
}}
==Алгоритм==
