Изменения

1.) # Тривиальный детерминированный алгоритм имеет временную сложность <tex>O(n^2)</tex>, и его суть заключается в проверке попарного пересечения отрезков. 2.) # Сложнее, но эффективнее алгоритм Бентли-Оттмана <ref>[http://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_Бентли-Оттмана ''Алгоритм Бентли-Оттмана'']</ref> с оценкой сложности <tex>O((n + k)\ log(n)+k)</tex>, в основе которого лежит метод заметающей прямой. 3.) # Алгоритм, предложенный Чазелле и Едельсбруннером <ref>[http://www.cs.princeton.edu/~chazelle/pubs/IntersectLineSegments.pdf ''An optimal algorithm for intersecting line segments in the plane'']</ref>, имеет лучшую оценку <tex>O(n\ log(n) + k)</tex>, но в отличие от предыдущих методов требует квадратичной памяти. 4.) # Оптимальный детерминированный алгоритм был предложен Балабаном <ref>[http://www.cs.sfu.ca/~binay/813.2011/Balaban.pdf ''I.J. Balaban. An optimal algorithm for finding segments intersections. In Proceedings of the Eleventh Annual Symposium on Computational Geometry, ACM Press, New York, 1995. - pp. 211–219.'']</ref> с временной оценкой сложности <tex>O(n\ log(n) + k)</tex> и <tex>O(n)</tex> памяти, где К - число пересекающихся отрезков.

Будем говорить, что отрезок <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> в других случаях.

Обозначения <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>s_1 <_a s_2</tex> если оба отрезка пересекают вертикальную линию <br> <tex>x = a</tex> иточка пересечения этой прямой с отрезком <tex>s_1</tex> лежит ниже точки пересечения с <tex>s_2</tex>.}}

− {{---}} любой отрезок из <tex>Q</tex> охватывает полосу <tex>\langle a, b \rangle</tex>; <br>− {{---}} нет пересечений отрезков внутри лестницы; <br>− {{---}} <tex>Q</tex> упорядочена по отношению <tex><_a</tex>.

добавить <tex>s_j</tex> в конец <tex>L’L';</tex>

[[Файл:Balaban_pic_2.png|280px|thumb|right|<tex>S_v = (\{s_1, s_2, s_3, s_4, s_5)\}</tex>, <tex>L_v = (s_1, s_3)</tex>, <tex>R_v = (s_4, s_3, s_4)</tex>, <tex>I_v = (\{s_2, s_5)\}</tex>]]