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

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

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

Введение

Решение задачи по поиску множества пересечений отрезков является одной из главных задач вычислительной геометрии. Тривиальный детерминированный алгоритм имеет временную сложность $O(n^2)$, и его суть заключается в проверке попарного пересечения отрезков. Сложнее, но эффективнее алгоритм Бентли-Оттмана с оценкой сложности $O((n + k)\ log(n)+k)$, в основе которого лежит метод заметающей прямой. Алгоритм, предложенный Чазелле и Едельсбруннером , имеет лучшую оценку $O(n\ log(n) + k)$, но в отличие от предыдущих методов требует квадратичной памяти. Оптимальный детерминированный алгоритм был предложен Балабаном с временной оценкой сложности $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 _b 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 _b 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$. (WAT??)

$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 := (Q_v, \langle a, b \rangle)$ будет полностью соотносима множеству $S_v'$;
    Найдем $Int(D_v, S_v')$;
    $c := \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)$;
$\}$

Отсюда и дальше $ls(v)$, $rs(v)$ и $ft(v)$ означают, соответственно, левого сына, правого сына, и отцовскую вершину узла <tex>v<.tex>.

Литература

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