Изменения

Решение задачи по поиску множества пересечений отрезков является одной из главных задач вычислительной геометрии. Рассмотрим несколько самых распространенных алгоритмов: # Тривиальный детерминированный алгоритм имеет временную сложность <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 <_b _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>Ends_{a, b}(S)</tex> это число вершин отрезков из <tex>S</tex>, находящихся в пределах полосы <tex>\langle a, b \rangle</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>.

Пусть <tex>L = (s_1 ,..., s_k)</tex>, где <tex>s_i <_b _a s_{i+1}</tex> <tex>Split_{a,b}(L, Q, L')</tex>

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

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

Предположим, что все отрезки лежат в полосе <tex>\langle a, b \rangle</tex>. Таким образом в самом начале у нас есть пара <tex>(S, \langle a, b, \rangle)</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>;

'''return''';

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

<tex>c := \leftarrow \lfloor (a + b)/2 \rfloor</tex>;

Наша задача показать, что все операции с узлом <tex>v</tex> происходят за <tex>O(|S_v) | + |Int(D_v, S_v')| + (a_v - b_v)logN)</tex>, и чтобы показать это, для этого возьмем во внимание, что <tex>\sum_v |S_v| = O(N \cdot logN + K)</tex> (очевидно, что <tex>\sum_v |Int(D_v, S_v')| \le K</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)</tex>, <tex>I_v = \{s_2, s_5\}</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>Split</tex> для множества <tex>L_v</tex> и построить <tex>Q_v</tex> за <tex>O(|L_v|) = O(|S_v|)</tex> времени. Но мы натыкаемся на новую проблему: передавая множества <tex>L_v</tex>, <tex>I_v</tex> и <tex>R_v</tex>, необходимо найти соответствующие множества сыновей узла <tex>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>IntersectingPairs(S_0)</tex> <tex>\{</tex> Отсортируем <tex>2N</tex> концов отрезков по абсциссе и найдем <tex>p_i</tex>, <tex>s(i)</tex> где <tex>i = 1, ..., 2N</tex>; <tex>L_r \leftarrow (s(1))</tex>; <tex>I_r \leftarrow S_0 \setminus (\{s(1)\} \cup \{s(2N)\})</tex>; <tex>TreeSearch(L_r, I_r, 1, 2N, R_r)</tex>; <tex>\}</tex>  <tex>TreeSearch(L_v, I_v, a, b, R_v)</tex> <tex>\{</tex> '''if''' <tex>b - a = 1</tex> '''then''' <tex>\{</tex> <tex>SearchInStrip_{a, b}(L_v, R_v)</tex>; '''return'''; <tex>\}</tex> <tex>Split_{a, b}(L_v, Q_v, L_{ls(v)})</tex>; <tex>D_v \leftarrow (Q_v, \langle a, b \rangle)</tex>; Найдем <tex>Int(D_v, L_{ls(v)})</tex>; <tex>c \leftarrow \lfloor (a + b) / 2 \rfloor</tex>; Разделяем отрезки из <tex>I_v</tex> внутренние для полосы <tex>\langle a, c \rangle</tex> во множество <tex>I_{ls(v)}</tex> внутренние для полосы <tex>\langle c, b \rangle</tex> во множество <tex>I_{rs(v)}</tex> <tex>TreeSearch(L_{ls(v)}, I_{ls(v)}, a, c, R_{ls(v)})</tex>; '''if''' <tex>p_c</tex> левый конец отрезка <tex>s(c)</tex> '''then''' <tex>L_{rs(v)} \leftarrow</tex> вставить <tex>s(c)</tex> в <tex>R_{ls(v)}</tex> '''else''' <tex>L_{rs(v)} \leftarrow</tex> удалить <tex>s(c)</tex> из <tex>R_{ls(v)}</tex> <tex>TreeSearch(L_{rs(v)}, I_{rs(v)}, c, b, R_{rs(v)})</tex>; Найдем <tex>Int(D_v, R_{rs(v)})</tex>; '''for''' <tex>s \in I_v</tex> '''do''' Найдем <tex>Loc(D_v, s)</tex> используя двоичный поиск; Найдем <tex>Int(D_v, I_v)</tex> используя значения, полученные шагом выше; <tex>R_v \leftarrow Merge_b(Q_v, R_{rs(v)})</tex>; <tex>\}</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> при поиске <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>. В итоге для работы алгоритма требуется <tex>O(N)</tex> памяти. {{Лемма|id=lemma2|about=#2|statement=<tex>\forall v \in V \ |S_v'| \le a_v - b_v + |Int(D_v, S_v')|</tex>.|proof=Утверждение напрямую вытекает из [[#lemma1|первой леммы]] и очевидного факта, что для любого множества <tex>S \subset S_0</tex>, количество концов отрезков, лежащих в полосе <tex>\langle a_v, b_v \rangle</tex>, меньше чем <tex>b_v - a_v</tex>.}} {{Теорема|about=#1|statement=<tex>\sum_{v \in V} |S_v'| \le 2N \lceil logN + 1 \rceil + K</tex>|proof=Утверждение напрямую вытекает из [[#lemma2|леммы №2]] и следующего отношения <tex>\sum_v (b_v - a_v) \le 2N \lceil logN + 1 \rceil</tex>.}} Обозначим множество всех вершин рекурсивного дерева за <tex>RT</tex>. {{Теорема|about=#2|statement=<tex>\sum_{v \in RT} |S_v| \le N \lceil 4logN + 5 \rceil + 2K</tex>|proof=Для всех узлов, кроме корня <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_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>. Для внутренних же узлов, время требуемое для поиска <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>. Соответственно в оптимальном алгоритме Балабана <tex>Loc(D_v, s)</tex> находится за <tex>O(1)</tex>.