Изменения

Решение задачи по поиску множества пересечений отрезков является одной из главных задач вычислительной геометрии. Рассмотрим несколько самых распространенных алгоритмов: # Тривиальный детерминированный алгоритм имеет временную сложность <tex>O(n^2)</tex>, и его суть заключается в проверке попарного пересечения отрезков.# Сложнее, но эффективнее алгоритм Бентли-Оттмана <ref>[http://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_Бентли-Оттмана ''Алгоритм Бентли-Оттмана'']</ref> с оценкой сложности <tex>O((n + k)\ log(n)+k)</tex>, в основе которого лежит метод заметающей прямой.# Алгоритм, предложенный Чазелле и Едельсбруннером <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>, но в отличие от предыдущих методов требует квадратичной памяти.# Оптимальный детерминированный алгоритм был предложен Балабаном <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> памяти, где К - число пересекающихся отрезков.  При количестве отрезков от 2000, и большому количеству пересечений целесообразно использовать алгоритм Балабана. Однако в результате громоздкости и высокой сложности реализации алгоритма, в большинстве практических задач используется алгоритм заметающей прямой Бентли-Оттмана.

Будем говорить, что отрезок <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>D</tex> полностью соотносима множеству полна относительно множества отрезков <tex>S</tex>, где <tex>S</tex> состоит из отрезков, пересекающих полосу <tex>\langle a, b \rangle</tex>, тогда <tex>|S| \le Ends_{a, b}(S) + |Int(D, S)|</tex>,<br>

Функция <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>S</tex> ''распадается'' в подмножества <tex>Q</tex> и <tex>S'</tex>, после чего лестница <tex>D = (Q, \langle a, b \rangle)</tex> становится полностью соотносимой множеству полной относительно множества <tex>S'</tex>. Необходимо найти пересечения отрезков из <tex>D</tex> и <tex>S'</tex>, затем, все пересечения в <tex>S'</tex>. Чтобы найти пересечения отрезков в <tex>S'</tex>, мы ''режем'' полосу <tex>\langle a, b \rangle</tex> и множество <tex>S'</tex> по вертикале <tex>x = c</tex> на полосы <tex>\langle a, c \rangle</tex>, <tex>\langle c, b \rangle</tex> и множества <tex>S'_{ls}</tex>, <tex>S'_{rs}</tex> соответственно, где <tex>c </tex> является медианой вершин отрезков, между <tex>a</tex> и <tex>b</tex>. Затем мы рекурсивно вызываем функцию к парам <tex>(S'_{ls}, \langle a, c \rangle)</tex> и <tex>(S'_{rs}, \langle c, b \rangle)</tex>. Ключевым является тот факт, что согласно [[#lemma1|лемме]] <tex>|S'| \le Ends_{a, b}(S') + |Int(D, S')|</tex>, таким образом, число дополнительных отрезков, появляющихся после ''разрезаний'' пропорционально числу найденных пересечений.

===Основы алгоритмаКлючевые моменты===

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

Основная задача нашего алгоритма, это рекурсивная функция <tex>TreeSearch</tex>. Мы соединяем Соединим каждый вызов функции с узлом некоего двоичного дерева (далее ''рекурсивное дерево''). Мы отмечаем Соответствующим узлом отметим все значения, множества и параметры вызова соответствующим узлом. В результате, мы проанализируем наш алгоритм рекурсивного дерева. Обозначим множество всех вершин рекурсивного дерева за <tex>RT</tex>, а множество внутренних вершин за <tex>V</tex>.

<tex>IntersectingPairs(S_v, a, bS_0):</tex>

<tex>TreeSearch(S_rS_v, a, b):</tex>

<tex>L \leftarrow</tex> отсортируем <tex>S_v</tex> по отношению <tex><_b_a</tex>;

<tex>D_v \leftarrow (Q_v, \langle a, b \rangle)</tex> будет полностью соотносима множеству полной, относительно множества <tex>S_v'</tex>;

[[Файл:Balaban_pic_2.png|280px|thumb|right|Отсюда и дальше <tex>ls(v)</tex>, <tex>rs(v)</tex> и <tex>S_v = ft(s_1v)</tex> означают, s_2соответственно, s_3левого сына, s_4правого сына, s_5)и отцовскую вершину узла <tex>v</tex>.Наша задача показать, что все операции с узлом <tex>L_v = v</tex> происходят за <tex>O(|S_v| + |Int(s_1D_v, s_3S_v')| + (a_v - b_v)logN)</tex>, для этого возьмем во внимание, что <tex>R_v \sum_v |S_v| = O(s_3, s_4N \cdot logN + K)</tex>(очевидно, что <tex>I_v = \sum_v |Int(s_2D_v, s_5S_v')| \le K</tex>]]).

Отсюда и дальше [[Файл:Balaban_pic_2.png|280px|thumb|right|<tex>ls(v)</tex>S_v = \{s_1, <tex>rs(v)</tex> и <tex>ft(v)</tex> означаютs_2, соответственноs_3, левого сынаs_4, правого сына, и отцовскую вершину узла <tex>vs_5\}</tex>.Наша задача показать, что все операции с узлом <tex>v</tex> происходят за <tex>OL_v = (|S_v) + |Int(D_vs_1, S_v')| + (a_v - b_v)logNs_3)</tex>, и чтобы показать это, возьмем во внимание, что <tex>\sum_v |S_v| R_v = O(N \cdot logN + Ks_4, s_3)</tex> (очевидно, что <tex>I_v = \sum_v |Int(D_v{s_2, S_v')| s_5\le K}</tex>).]]

множества <tex>L_v</tex> упорядоченного по отношению <tex><_a</tex>, неупорядоченного множества <tex>I_v</tex>, и множества <tex>R_v</tex> упорядоченного по отношению <tex><_b</tex>. Расположим отрезки из <tex>S_v</tex>, пересекающие границу <tex>x = a</tex> во множество <tex>L_v</tex>, отрезки пересекающие <tex>x = b</tex> во множество <tex>R_v</tex>, и внутренние отрезки во множество <tex>I_v</tex> (пример на ''рисунке справа'').

Неупорядоченные множества <tex>I_{ls(v)}</tex> и <tex>I_{rs(v)}</tex> строятся легко. Множество <tex>L_{ls(v)}</tex> будет найдено вызовом функции <tex>Split_{a, b}(L_v, Q_v, L_{ls(v)})</tex> для третьего шага нахождения <tex>Int(D_v, S_v')</tex> в функции <tex>TreeSearch</tex>. Множество <tex>L_{rs(v)}</tex> получается из <tex>R_{ls(v)}</tex> за линейное время вставкой (если <tex>p_c</tex> левый конец левая вершина отрезка) или удалением (если <tex>p_c</tex> правый конец правая вершина отрезка) отрезка <tex>s(c)</tex>. Но как получить <tex>R_{ls(v)}</tex> из <tex>L_v</tex>, <tex>R_v</tex> и <tex>I_v</tex> без сортировки?

Для листьев мы сделаем проверку вначале, и получим <tex>R_v</tex> из <tex>L_v</tex>. Пусть <tex>L_v</tex> и <tex>I_v</tex> известны, и все сыновья узла <tex>v</tex> - листья. Для начала запустим функцию <tex>Split(L_v, Q_v, L_{ls(v)})</tex> и найдем <tex>Q_v</tex> и <tex>L_{ls(v)}</tex>. Теперь мы должны найти <tex>Int(D_s, S_v') = Int(D_v, L_{ls(v)}) \cup Int(D_v, I_v) \cup Int(D_v, R_{rs(v)})</tex>, но мы не знаем <tex>R_{rs(v)}</tex>и, и соответственно , можем найти только <tex>Int(D_v, L_{ls(v)}) \cup Int(D_v, I_v)</tex>. Применим <tex>SearchInStrip</tex> к множеству <tex>L_{ls(v)}</tex> и получим <tex>R_{ls(v)}</tex>. Множество <tex>L_{rs(v)}</tex> получается из <tex>R_{ls(v)}</tex> вставкой или удалением отрезка <tex>s(c)</tex>. Применим <tex>SearchInStrip</tex> к <tex>L_{rs(v)}</tex> и найдем <tex>R_{rs(v)}</tex>. Теперь можем продолжить вычисление <tex>Int(D_v, R_{rs(v)})</tex> и получим <tex>R_v</tex> слиянием <tex>Q_v</tex> и <tex>R_{rs(v)}</tex>.

Разделяем отрезки из <tex>I_v</tex>

Заметим, что нахождение <tex>Int(D_v, R_{rs(v)})</tex> надо делать аккуратно, так как множества <tex>R_{rs(v)}</tex> и <tex>L_{ls(v)}</tex> могут иметь одни и те же отрезки (которые '''пересекают''' <tex>\langle a, b \rangle</tex>). Мы нашли их пересечения с <tex>D_v</tex> на 3ем шагепри поиске <tex>Int(D_v, L_{ls(v)})</tex>, и не должны вывести эти пересечения снова. ==Время работы==

Для начала рассчитаем место, необходимое для выполнения алгоритма. Алгоритм использует рекурсивную функцию <tex>TreeSearch</tex>. Последовательность вызовов функции может занять память. Эта последовательность может быть представлена как путь корня рекурсивного дерева, до узла. Назовем этот узел, и соответствующий вызов ''активным''. Активный Соответствующий вызов этого узла занимает <tex>O(N)</tex> памяти, каждый его "предок" занимает <tex>O(|I_v| + |Q_v|)</tex> памяти, а остальные структуры используют <tex>O(N)</tex>. Очевидно, что любой путь <tex>pt</tex> от корня рекурсивного дерева до какого-то узла <tex>\sum_{v \in pt}(|I_v + |Q_v|) = O(N)(|I_v| \le b_v - a_v \le \lceil (b_{ft(v)} - a_{ft(v)})/2 \rceil)</tex>.

Утверждение напрямую вытекает из [[#lemma1|первой леммы]] (далее лемма №1) и очевидного факта, что для любого множества <tex>S \subset S_0</tex>, количество концов отрезков, лежащих в полосе <tex>\langle a_v, b_v \rangle</tex>, меньше чем <tex>b_v - a_v</tex>.

Для всех узлов, кроме корня <tex>r</tex> имеет место выражение <tex>|S_v| \le |S_{ft(v)}'|</tex>, следовательно <tex>\sum_{v \in RT} |S_v| \le |S_r| + \sum_{v \in RT \setminus r} |S_{ft(v)}| \le N + 2 \sum_{v \in V} |s_vS_v'| \le N \lceil 4 logN + 5 \rceil + 2K</tex>.

Начальная сортировка и инициализация множеств <tex>L_r</tex> и <tex>I_r</tex> может быть произведена за <tex>O(N logN)</tex> времени. Время работы функции <tex>TreeSearch</tex> является суммой длительностей всех его вызовов. Каждый вызов от внешних узлов добавляет к этой сумме <tex>O(|L_v| + |Int_{a, b}(L_v)|)</tex>. Для внутренних же узлов, время требуемое для выполнения 10го шага алгоритма поиска <tex>Loc(D_v, s)</tex> равно <tex>O(|I_v| log N)</tex>, а для остальных <tex>O(|S_v| + |Int(D_v, S_v')|)</tex>. Если мы все это сложим, то придем к выводу, что наш алгоритм работает за <tex>O(N log^2 N + K)</tex>. Заметим, что его скорость можно увеличить до <tex>O(N logN + K)</tex>, если не будем учитывать время нахождения <tex>Loc(D_v, s)</tex>.