Алгоритм Балабана — различия между версиями

Версия 16:21, 15 ноября 2013

Эта статья находится в разработке!

Алгоритм Балабана — детерминированный алгоритм, позволяющий по множеству отрезков на плоскости получить множество точек, в которых эти отрезки пересекаются.

Содержание

[убрать]

1 Введение
2 Основные понятия
3 Алгоритм
4 Время работы
5 Примечания
6 Литература

Введение

Решение задачи по поиску множества пересечений отрезков является одной из главных задач вычислительной геометрии. Тривиальный детерминированный алгоритм имеет временную сложность $O(n^2)$ , и его суть заключается в проверке попарного пересечения отрезков. Сложнее, но эффективнее алгоритм Бентли-Оттмана ^[1] с оценкой сложности $O((n + k)\ log(n)+k)$ , в основе которого лежит метод заметающей прямой. Алгоритм, предложенный Чазелле и Едельсбруннером ^[2], имеет лучшую оценку $O(n\ log(n) + k)$ , но в отличие от предыдущих методов требует квадратичной памяти. Оптимальный детерминированный алгоритм был предложен Балабаном ^[3] с временной оценкой сложности $O(n\ log(n) + k)$ и $O(n)$ памяти, где К - число пересекающихся отрезков. При количестве отрезков от 2000, и большому количеству пересечений целесообразно использовать алгоритм Балабана. Однако в результате громоздкости и высокой сложности реализации алгоритма, в большинстве практических задач используется алгоритм заметающей прямой Бентли-Оттмана.

Основные понятия

Введем некоторые обозначения. Пусть $Int(S)$ - множество всех точек пересечения отрезков из множества $S$ , а $K = |Int(S)|$ - количество таких пересечений ;
Через $\langle a, b \rangle$ обозначим вертикальную полосу, которая ограничена прямыми $x = a$ и $x = b$ , а через $s$ — отрезок с вершинами в точках с абсциссами $l$ и $r$ .
Рассмотрим взаимное расположение вертикальной полосы $\langle a, b \rangle$ и отрезка $s$ .

Определение:

Будем говорить, что отрезок

$s$ , с вершинами в точках с абсциссами

$l$ и

$r$ :

- содержит(span) полосу $\langle a, b \rangle$ , если $l \le a \le b \le r$ ;
- внутренний(inner) для полосы $\langle a, b \rangle$ , если $a \lt l \lt r \lt b$ ;

- пересекает(cross) полосу

$\langle a, b \rangle$ в других случаях.

Определение:

Два отрезка

$s_1$ и

$s_2$ называются пересекающимися внутри полосы

$\langle a, b \rangle$ , если их точка пересечения лежит в пределах этой полосы.
Для двух множеств отрезков

$S$ и

$S'$ определим множество

$Int(S, S')$ как

$\{ {s, s'} | (s \in S, s' \in S') \& (s \ intersect \ s') \}$ .

$D = ((s_1, s_2, s_3), \langle a, b \rangle)$ ,

$Loc(D, s_4) = 0$ ,

$Loc(D, s_5) = 2$ или

$3$ ,

$Int(D, \{s_4,\ s_5\}) = \{\{s_3,\ s_5\}\}$

Обозначения $Int_{a, b}(S)$ и $Int_{a, b}(S, S')$ будут использоваться для описания подмножеств $Int(S)$ и $Int(S, S')$ , состоящих из пересекающихся пар отрезков в пределах полосы $\langle a, b \rangle$ . Далее скобки $\{\}$ используются для определения неупорядоченных множеств, а скобки $()$ используются для определения упорядоченных множеств.

Введем отношение порядка на множестве отрезков $s_1 \lt _a s_2$ если оба отрезка пересекают вертикальную линию $x = a$ и точка пересечения этой прямой с отрезком $s_1$ лежит ниже точки пересечения с $s_2$ .

Определение:

Лестница

$D$ — это пара

$(Q, \langle a, b \rangle)$ , в которой отрезки из множества

$Q$ удовлетворяют следующим условиям :

− любой отрезок из $Q$ содержит полосу $\langle a, b \rangle$ ;
− нет пересечений отрезков внутри лестницы;
− $Q$ упорядочена по отношению $\lt _a$ .

Часть отрезков лестницы внутри полосы будем называть ступеньками.

Определение:

Будем называть лестницу

$D$ полностью соотносимой множеству отрезков

$S$ , если каждый отрезок из

$S$ либо не пересекает полосу

$\langle a, b \rangle$ , либо пересекает хотя бы одну из ступенек из множества

$D$ .

Лемма:

Пусть лестница

$D$ полностью соотносима множеству отрезков

$S$ , где

$S$ состоит из отрезков, пересекающих полосу

$\langle a, b \rangle$ , тогда

$|S| \le Ends_{a, b}(S) + |Int(D, S)|$ ,
где

$Ends_{a, b}(S)$ это число вершин отрезков из

$S$ , находящихся в пределах полосы

$\langle a, b \rangle$ .

Определение:

Если точка

$p$ отрезка

$s$ лежит между ступеньками

$i$ и

$i + 1$ , тогда число

$i$ называется местоположением

$s$ на лестнице

$D$ и обозначается как

$Loc(D, s)$

Утверждение:

Имея лестницу

$D = (Q, \langle a, b \rangle)$ и множество отрезков

$S$ , множество

$Int(D, S)$ можно найти за время

$O(|S| log|Q| + |Int(D, S)|)$ .
Однако, если

$S’$ упорядочено отношением

$\lt _x$ , где

$x \in [a, b]$ , тогда можно найти

$Int(D, S)$ за время

$O(|S| + |Q| + |Int(D, S)|)$ .

Алгоритм

Введем несколько дополнительных функций, чтобы упростить основной алгоритм:

Split

Функция $Split$ разделяет входное множество отрезков $L$ , пересекающих некоторую полосу $\langle a, b \rangle$ , на подмножества $Q$ и $L'$ так, что лестница $(Q, \langle a, b \rangle)$ полностью соотносима множеству отрезков $L'$ .

Пусть  $L = (s_1 ,..., s_k)$ , где  $s_i \lt _a s_{i+1}$ 
 $Split_{a, b}(L, Q, L')$ 
 $\{$ 
     $L' \leftarrow \varnothing; Q \leftarrow \varnothing$ 
    for  $j = 1,...,k$  do
        if отрезок  $S_j$  не пересекает
        последний отрезок из  $Q$  внутри полосы  $\langle a, b \rangle$ 
        и при этом содержит её then
            добавить  $s_j$  в конец  $Q;$ 
        else
            добавить  $s_j$  в конец  $L’;$ 
 $\}$

Эта функция работает за $O(|L|)$ времени.

Search In Strip

Зная $L$ мы можем найти $Int_{a, b}(L)$ и $R$ используя следующую рекурсивную функцию:

 $SearchInStrip_{a, b}(L, R)$ 
 $\{$ 
     $Split(L, Q, L');$  
    if  $L' = \varnothing$  then
         $R \leftarrow Q;$  
        return $;$ 
    Найдем  $Int_{a, b}(Q, L');$ 
     $SearchInStrip_{a, b} (L', R');$ 
     $R \leftarrow Merge_b(Q, R’);$ 
 $\}$

Здесь, $Merge_x(S_1, S_2)$ это функция объединения множеств $S_1$ и $S_2$ , упорядоченных по отношению $\lt _x$ . Время выполнения $SearchInStrip$ эквивалентно сумме времён каждого её запуска. Очевидно, что время работы $i$ -той функции, будет равно $O(|L_i| + |Int_{a, b}(Q_i, {L_i}')|)$ , где $L_i, Q_i, {L_i}'$ это соответствующие наборы $(L_0 = L, L_{i+1} = {L_i}')$ .

Учитывая лемму, заключаем, что функция $SearchInStrip_{a, b}(L, R)$ работает за $O(|L| + |Int_{a, b}(L)|)$ .

Предположим, что все отрезки лежат в полосе $\langle a, b\rangle$ . Таким образом в самом начале у нас есть пара $(S, \langle a, b\rangle)$ . Что же дальше происходит: множество $S$ распадается в подмножества $Q$ и $S'$ , после чего лестница $D = (Q, \langle a, b \rangle)$ становится полностью соотносимой множеству $S'$ . Необходимо найти пересечения отрезков из $D$ и $S'$ , затем, все пересечения в $S'$ . Чтобы найти пересечения отрезков в $S'$ , мы режем полосу $\langle a, b \rangle$ и множество $S'$ по вертикале $x = c$ на полосы $\langle a, c \rangle$ , $\langle c, b \rangle$ и множества $S'_{ls}$ , $S'_{rs}$ соответственно, где c является медианой вершин отрезков, между $a$ и $b$ . Затем мы рекурсивно вызываем функцию к парам $(S'_{ls}, \langle a, c \rangle)$ и $(S'_{rs}, \langle c, b \rangle)$ . Ключевым является тот факт, что согласно лемме $|S'| \le Ends_{a, b}(S') + |Int(D, S')|$ , таким образом, число дополнительных отрезков, появляющихся после разрезаний пропорционально числу найденных пересечений.

Основы алгоритма

Давайте разберемся с алгоритмом более подробно:

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

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

 $IntersectingPairs(S_v, a, b):$ 
    Отсортируем  $2 \cdot N$  вершин по координатам и
        найдем  $p_i, s(i), i = 1,...,2 \cdot N;\ S_r \leftarrow S_0$ 
     $TreeSearch(S_r, 1, 2 \cdot N)$ ;

 $TreeSearch(S_r, a, b):$ 
 $\{$ 
    if  $b - a = 1$  then
     $\{$ 
         $L \leftarrow$  отсортируем  $S_v$  по отношению  $\lt _b$ ;
         $SearchInStrip_{a, b}(L_v, R_v)$ ; 
        return;
     $\}$ 
    Разделим  $S_v$  на  $Q_v$  и  $S_v'$  так, что лестница
         $D_v \leftarrow (Q_v, \langle a, b \rangle)$  будет полностью соотносима множеству  $S_v'$ ;
    Найдем  $Int(D_v, S_v')$ ;
     $c \leftarrow \lfloor (a + b)/2 \rfloor$ ;
    Разделим отрезки из  $S_v'$  на пересекающих
        полосу  $\langle a, c \rangle$   $S_{ls}(v)$  и
        полосу  $\langle c, b \rangle$   $S_{rs}(v)$ ;
     $TreeSearch(S_{ls}(v), a, c)$ ;
     $TreeSearch(S_{rs}(v), c, b)$ ;
 $\}$

$S_v = (s_1, s_2, s_3, s_4, s_5)$ ,

$L_v = (s_1, s_3)$ ,

$R_v = (s_3, s_4)$ ,

$I_v = (s_2, s_5)$

Отсюда и дальше $ls(v)$ , $rs(v)$ и $ft(v)$ означают, соответственно, левого сына, правого сына, и отцовскую вершину узла $v$ . Наша задача показать, что все операции с узлом $v$ происходят за $O(|S_v) + |Int(D_v, S_v')| + (a_v - b_v)logN)$ , и чтобы показать это, возьмем во внимание, что $\sum_v |S_v| = O(N \cdot logN + K)$ (очевидно, что $\sum_v |Int(D_v, S_v')| \le K$ ).

Функция $TreeSearch$ похожа на функцию $SearchInStrip$ . Основная разница заключается в том, что $SearchInStrip$ вызывает себя без изменения полосы, когда $TreeSearch$ делит полосу на две части, после чего рекурсивно вызывает себя для них. Другое отличие заключается в том, что множество $S_v$ не упорядочено так же, как $L$ . В результате мы не можем напрямую использовать функцию $Split$ для эффективного деления $S_v$ .

Чтобы решить эту проблему, представим $S_v$ как объединение трех множеств: множества $L_v$ упорядоченного по отношению $\lt _a$ , неупорядоченного множества $I_v$ , и множества $R_v$ упорядоченного по отношению $\lt _b$ . Расположим отрезки из $S_v$ , пересекающие границу $x = a$ во множество $L_v$ , отрезки пересекающие $x = b$ во множество $R_v$ , и внутренние отрезки во множество $I_v$ (пример на рисунке справа).

Теперь мы можем вызвать функцию $Split$ для множества $L_v$ и построить $Q_v$ за $O(|L_v|) = O(|S_v|)$ времени. Но мы натыкаемся на новую проблему: передавая множества $L_v$ , $I_v$ и $R_v$ , необходимо найти соответствующие множества сыновей узла $v$ .

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

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

Конечная функция будет выглядеть так:

 $IntersectingPairs(S_0)$ 
 $\{$ 
    Отсортируем  $2N$  концов отрезков по абсциссе
        и найдем  $p_i$ ,  $s(i)$  где  $i = 1, ..., 2N$ ;
     $L_r \leftarrow (s(1))$ ;  $I_r \leftarrow S_0 \setminus (\{s(1)\} \cup \{s(2N)\})$ ;
     $TreeSearch(L_r, I_r, 1, 2N, R_r)$ ;
 $\}$

 $TreeSearch(L_v, I_v, a, b, R_v)$ 
 $\{$ 
    if  $b - a = 1$  then
     $\{$ 
         $SearchInStrip_{a, b}(L_v, R_v)$ ;
        return;
     $\}$ 
     $Split_{a, b}(L_v, Q_v, L_{ls(v)})$ ;
     $D_v \leftarrow (Q_v, \langle a, b \rangle)$ ;
    Найдем  $Int(D_v, L_{ls(v)})$ ;
     $c \leftarrow \lfloor (a + b) / 2 \rfloor$ ;
   Разделяем отрезки из  $I_v$ 
       внутренние для полосы  $\langle a, c \rangle$  во множество  $I_{ls(v)}$ 
       внутренние для полосы  $\langle c, b \rangle$  во множество  $I_{rs(v)}$ 
     $TreeSearch(L_{ls(v)}, I_{ls(v)}, a, c, R_{ls(v)})$ ;
    if  $p_c$  левый конец отрезка  $s(c)$  then
         $L_{rs(v)} \leftarrow$  вставить  $s(c)$  в  $R_{ls(v)}$ 
    else
         $L_{rs(v)} \leftarrow$  удалить  $s(c)$  из  $R_{ls(v)}$ 
     $TreeSearch(L_{rs(v)}, I_{rs(v)}, c, b, R_{rs(v)})$ ;
    Найдем  $Int(D_v, R_{rs(v)})$ ;
    for  $s \in I_v$  do
        Найдем  $Loc(D_v, s)$  используя двоичный поиск;
    Найдем  $Int(D_v, I_v)$  используя значения, полученные шагом выше;
     $R_v \leftarrow Merge_b(Q_v, R_{rs(v)})$ ;
 $\}$

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

Для начала рассчитаем место, необходимое для выполнения алгоритма. Алгоритм использует рекурсивную функцию $TreeSearch$ . Последовательность вызовов функции может занять память. Эта последовательность может быть представлена как путь корня рекурсивного дерева, до узла. Назовем этот узел, и соответствующий вызов активным. Активный вызов занимает $O(N)$ памяти, каждый его "предок" занимает $O(|I_v| + |Q_v|)$ памяти, а остальные структуры используют $O(N)$ . Очевидно, что любой путь $pt$ от корня рекурсивного дерева до какого-то узла .

В итоге для работы алгоритма требуется $O(N)$ памяти.

Время работы

Лемма (#2):

$\forall v \in V \ |S_v'| \le a_v - b_v + |Int(D_v, S_v')|$ .

Доказательство:

$\triangleright$

Утверждение напрямую вытекает из леммы (далее лемма №1) и очевидного факта, что для любого множества

$S \subset S_0$ , количество концов отрезков, лежащих в полосе

$\langle a_v, b_v \rangle$ , меньше чем

$b_v - a_v$ .

$\triangleleft$

Теорема (#1):

$\sum_{v \in V} |S_v'| \le 2N \lceil logN + 1 \rceil + K$

Доказательство:

$\triangleright$

Утверждение напрямую вытекает из леммы №2 и следующего отношения

$\sum_v (b_v - a_v) \le 2N \lceil logN + 1 \rceil$ .

$\triangleleft$

Теорема (#2):

$\sum_{v \in RT} |S_v| \le N \lceil 4logN + 5 \rceil + 2K$

Доказательство:

$\triangleright$

Для всех узлов, кроме корня

$r$ имеет место выражение

$|S_v| \le |S_{ft(v)}'|$ , следовательно

$\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$ .

$\triangleleft$

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

Соответственно в оптимальном алгоритме Балабана $Loc(D_v, s)$ находится за $O(1)$ .

Примечания

Литература

Т.Вознюк, В.Терещенко — К построению эффективного решения задачи пересечения отрезков
Ф.Препарата, М.Шеймос — Вычислительная геометрия

[1] Перейти ↑ Алгоритм Бентли-Оттмана

[2] Перейти ↑ An optimal algorithm for intersecting line segments in the plane

[3] Перейти ↑ 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.

[1]

[2]

[3]

@@ Строка 113: / Строка 113: @@
 Учитывая [[#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>\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> соответственно, где c является медианой вершин отрезков, между <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>, таким образом, число дополнительных отрезков, появляющихся после ''разрезаний'' пропорционально числу найденных пересечений.

Алгоритм Балабана — различия между версиями

Версия 16:21, 15 ноября 2013

Содержание

Введение

Основные понятия

Алгоритм

Split

Search In Strip

Основы алгоритма

Время работы

Примечания

Литература

Навигация

Персональные инструменты

Пространства имён

Варианты

Просмотры

Ещё

Поиск

Навигация

Инструменты