Изменения

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

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

25 814 байт добавлено, 19:05, 4 сентября 2022
м
rollbackEdits.php mass rollback
{{В разработке}} '''Алгоритм Балабана''' {{---}} детерминированный алгоритм, позволяющий по множеству отрезков на плоскости получить множество точек, в которых эти отрезки пересекаются . <br>
==Введение==
Методы поиска Решение задачи по поиску множества пересечений отрезков разделяются на детерминированные и недетерминированныеявляется одной из главных задач вычислительной геометрии. Рассмотрим несколько самых распространенных алгоритмов: # Тривиальный детерминированный алгоритм имеет временную сложность <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>Int(S)</tex> - множество всех точек пересечения отрезков из множества <tex>S</tex>, а <tex>K = |Int(S)|</tex> - количество таких пересечений ;<br>Через <tex>\langle a, b \rangle</tex> обозначим вертикальную полосу, которая ограничена прямыми <tex>x = a</tex> и <tex>x = b</tex>, а через <tex>s</tex> {{---}} отрезок с вершинами в точках с абсциссами <tex>l</tex> и <tex>r</tex>.<br>Рассмотрим взаимное расположение вертикальной полосы <tex>\langle a, b \rangle</tex> и отрезка <tex>s</tex>.  {{Определение|definition=Будем говорить, что отрезок <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> в других случаях.}} {{Определение|definition=Два отрезка <tex>s_1</tex> и <tex>s_2</tex> называются ''пересекающимися внутри'' полосы <tex>\langle a, b \rangle</tex>, если их точка пересечения лежит в пределах этой полосы.<br> Для двух множеств отрезков <tex>S</tex> и <tex>S'</tex> определим множество <tex>Int(S, S')</tex> как <tex>\{ {s, s'} | (s \in S, s' \in S') \& (s \ intersect \ s') \}</tex>.}}[[Файл: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> используются для определения упорядоченных множеств. {{Определение|neat=neat|definition=Введем отношение порядка на множестве отрезков <tex>s_1 <_a s_2</tex> если оба отрезка пересекают вертикальную линию<br> <tex>x = a</tex> и точка пересечения этой прямой с отрезком <tex>s_1</tex> лежит ниже точки пересечения с <tex>s_2</tex>.}} {{Определение|neat=neat|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>. Часть отрезков лестницы внутри полосы будем называть '''ступеньками'''.}} {{Определение|definition=Будем называть лестницу <tex>D</tex> '''полной''' относительно множества отрезков <tex>S</tex>, если каждый отрезок из <tex>S</tex> либо не охватывает полосу <tex>\langle a, b \rangle</tex>, либо пересекает хотя бы одну из ступенек из множества <tex>D</tex>.}} {{Лемма|id=lemma1|statement=Пусть лестница <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>.}} {{Определение|definition=Если точка <tex>p</tex> отрезка <tex>s</tex> лежит между ступеньками <tex>i</tex> и <tex>i + 1</tex>, тогда число <tex>i</tex> называется ''местоположением'' <tex>s</tex> на лестнице <tex>D</tex> и обозначается как <tex>Loc(D, s)</tex>}} {{Утверждение|statement=Имея лестницу <tex>D = (Q, \langle a, b \rangle)</tex> и множество отрезков <tex>S</tex>, множество <tex>Int(D, S)</tex> можно найти за время <tex>O(|S| log|Q| + |Int(D, S)|)</tex>. <br>Однако, если <tex>S’</tex> упорядочено отношением <tex><_x</tex>, где <tex>x \in [a, b]</tex>, тогда можно найти <tex>Int(D, S)</tex> за время <tex>O(|S| + |Q| + |Int(D, S)|)</tex>.}}
==Алгоритм==
 
Введем несколько дополнительных функций, чтобы упростить основной алгоритм:
 
===Split===
 
Функция <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 <_a s_{i+1}</tex>
<tex>Split_{a, b}(L, Q, L')</tex>
<tex>\{</tex>
<tex>L' \leftarrow \varnothing; Q \leftarrow \varnothing</tex>
'''for''' <tex>j = 1,...,k</tex> '''do'''
'''if''' отрезок <tex>S_j</tex> не пересекает
последний отрезок из <tex>Q</tex> внутри полосы <tex>\langle a, b \rangle</tex>
и при этом охватывает её '''then'''
добавить <tex>s_j</tex> в конец <tex>Q;</tex>
'''else'''
добавить <tex>s_j</tex> в конец <tex>L';</tex>
<tex>\}</tex>
 
Эта функция работает за <tex>O(|L|)</tex> времени.
 
===Search In Strip===
 
Зная <tex>L</tex> мы можем найти <tex>Int_{a, b}(L)</tex> и <tex>R</tex> используя следующую рекурсивную функцию:
 
<tex>SearchInStrip_{a, b}(L, R)</tex>
<tex>\{</tex>
<tex>Split(L, Q, L');</tex>
'''if''' <tex>L' = \varnothing</tex> '''then'''
<tex>R \leftarrow Q;</tex>
'''return'''<tex>;</tex>
Найдем <tex>Int_{a, b}(Q, L');</tex>
<tex>SearchInStrip_{a, b} (L', R');</tex>
<tex>R \leftarrow Merge_b(Q, R’);</tex>
<tex>\}</tex>
 
Здесь, <tex>Merge_x(S_1, S_2)</tex> это функция объединения множеств <tex>S_1</tex> и <tex>S_2</tex>, упорядоченных по отношению <tex><_x</tex>. Время выполнения <tex>SearchInStrip</tex> эквивалентно сумме времён каждого её запуска. Очевидно, что время работы <tex>i</tex>-той функции, будет равно <tex>O(|L_i| + |Int_{a, b}(Q_i, {L_i}')|)</tex>, где <tex>L_i, Q_i, {L_i}'</tex> это соответствующие наборы <tex>(L_0 = L, L_{i+1} = {L_i}')</tex>.
 
Учитывая [[#lemma1|лемму]], заключаем, что функция <tex>SearchInStrip_{a, b}(L, R)</tex> работает за <tex>O(|L| + |Int_{a, b}(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_0</tex>, а через <tex>s(i)</tex> отрезок, которому он принадлежит соответственно.
 
Основная задача нашего алгоритма, это рекурсивная функция <tex>TreeSearch</tex>. Соединим каждый вызов функции с узлом некоего двоичного дерева (далее ''рекурсивное дерево''). Соответствующим узлом отметим все значения, множества и параметры вызова. Обозначим множество внутренних вершин за <tex>V</tex>.
 
<tex>IntersectingPairs(S_0):</tex>
Отсортируем <tex>2 \cdot N</tex> вершин по координатам и
найдем <tex>p_i, s(i), i = 1,...,2 \cdot N;\ S_r \leftarrow S_0</tex>
<tex>TreeSearch(S_r, 1, 2 \cdot N)</tex>;
 
<tex>TreeSearch(S_v, a, b):</tex>
<tex>\{</tex>
'''if''' <tex>b - a = 1</tex> '''then'''
<tex>\{</tex>
<tex>L \leftarrow</tex> отсортируем <tex>S_v</tex> по отношению <tex><_a</tex>;
<tex>SearchInStrip_{a, b}(L_v, R_v)</tex>;
'''return''';
<tex>\}</tex>
Разделим <tex>S_v</tex> на <tex>Q_v</tex> и <tex>S_v'</tex> так, что лестница
<tex>D_v \leftarrow (Q_v, \langle a, b \rangle)</tex> будет полной, относительно множества <tex>S_v'</tex>;
Найдем <tex>Int(D_v, S_v')</tex>;
<tex>c \leftarrow \lfloor (a + b)/2 \rfloor</tex>;
Разделим отрезки из <tex>S_v'</tex> на пересекающих
полосу <tex>\langle a, c \rangle</tex> <tex>S_{ls}(v)</tex> и
полосу <tex>\langle c, b \rangle</tex> <tex>S_{rs}(v)</tex>;
<tex>TreeSearch(S_{ls}(v), a, c)</tex>;
<tex>TreeSearch(S_{rs}(v), c, b)</tex>;
<tex>\}</tex>
 
Отсюда и дальше <tex>ls(v)</tex>, <tex>rs(v)</tex> и <tex>ft(v)</tex> означают, соответственно, левого сына, правого сына, и отцовскую вершину узла <tex>v</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>TreeSearch</tex> похожа на функцию <tex>SearchInStrip</tex>. Основная разница заключается в том, что <tex>SearchInStrip</tex> вызывает себя без изменения полосы, когда <tex>TreeSearch</tex> делит полосу на две части, после чего рекурсивно вызывает себя для них. Другое отличие заключается в том, что множество <tex>S_v</tex> не упорядочено так же, как <tex>L</tex>. В результате мы не можем напрямую использовать функцию <tex>Split</tex> для эффективного деления <tex>S_v</tex>.
 
Чтобы решить эту проблему, представим <tex>S_v</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>.
==Примечания==
==Литература==
[http://www.graphicon.ru/proceedings/2010/conference/RU/Se4/021.pdf ''Т.Вознюк, В.Терещенко {{---}} К построению эффективного решения задачи пересечения отрезков'']<br>[http://booksshare.net/books/math/preparata-f/1989/files/vichgeometr.pdf ''Ф.Препарата, М.Шеймос {{---}} Вычислительная геометрия'']<br> 
[[Категория: Вычислительная геометрия]]
1632
правки

Навигация