Изменения

Перейти к: навигация, поиск

Алгоритм Балабана

101 байт добавлено, 11:03, 30 ноября 2013
Основные понятия
[[Файл:Balaban_pic_1.png|280px|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> используются для определения упорядоченных множеств.
Далее фигурные скобки <tex>\{\}</tex> используются для определения неупорядоченных множеств, а круглые скобки <tex>()</tex> используются для определения упорядоченных множеств. {{Определение|neat=neat|definition=Введем отношение порядка на множестве отрезков <tex>s_1 <_a s_2</tex> если оба отрезка пересекают вертикальную линию <br> <tex>x = a</tex> иточка пересечения этой прямой с отрезком <tex>s_1</tex> лежит ниже точки пересечения с <tex>s_2</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>.
Часть отрезков лестницы внутри полосы будем называть '''ступеньками'''.
Анонимный участник

Навигация