Изменения

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>D</tex> '''полной''' относительно множества отрезков <tex>S</tex>, если каждый отрезок из <tex>S</tex> либо не пересекает охватывает полосу <tex>\langle a, b \rangle</tex>, либо пересекает хотя бы одну из ступенек из множества <tex>D</tex>.

Функция <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>.

и при этом содержит охватывает её '''then'''

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

Не умаляя общности, предположим, что все пересечения и вершины отрезков имеют разные абсциссы (в конечном счете, их можно будет отсортировать введением дополнительных свойств). Будем рассматривать целые координаты на промежутке <tex>[1, 2N]</tex>. Пусть Обозначим через <tex>p_i</tex> и слева направо конец отрезка множества <tex>s(i)S_0</tex> будут координатами вершин , а через <tex>s(i)</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>]]