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

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

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

Введение

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

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

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

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

Будем говорить, что отрезок [math]s[/math], с концами абсцисс [math]l[/math] и [math]r[/math] : - содержит(span) полосу [math]\langle a, b \rangle[/math], если [math]l \le a \le b \le r[/math]; - внутренний(inner) для полосы [math]\langle a, b \rangle[/math], если [math]a \lt l \lt r \lt b[/math]; - пересекает(cross) полосу [math]\langle a, b \rangle[/math] в других случаях.

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

Два отрезка [math]s_1[/math] и [math]s_2[/math] называются пересекающимися внутри полосы [math]\langle a, b \rangle[/math], если их точка пересечения лежит в пределах этой полосы. Для двух множеств отрезков [math]S[/math] и [math]S'[/math] определим множество [math]Int(S, S')[/math] как [math]\{ {s, s'} | (s \in S, s' \in S') \& (s \ intersect \ s') \}[/math].

[math]D = ((s_1, s_2, s_3), \langle a, b \rangle)[/math], [math]Loc(D, s_4) = 0[/math], [math]Loc(D, s_5) = 2[/math] или [math]3[/math], [math]Int(D, \{s_4,\ s_5\}) = \{\{s_3,\ s_5\}\}[/math]

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

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

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

Лестница [math]D[/math] — это пара [math](Q, \langle a, b \rangle)[/math], в которой отрезки из множества [math]Q[/math] удовлетворяют следующим условиям :

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

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

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

Будем называть лестницу [math]D[/math] полностью соотносимой множеству отрезков [math]S[/math], если каждый отрезок из [math]S[/math] либо не пересекает полосу [math]\langle a, b \rangle[/math], либо пересекает хотя бы одну из ступенек из множества [math]D[/math].

Лемма:

Если лестница [math]D[/math] полностью соотносима множеству отрезков [math]S[/math], где [math]S[/math] состоит из отрезков, пересекающих полосу [math]\langle a, b \rangle[/math], тогда [math]|S| \le Ends_{a, b}(S) + |Int(D, S)|[/math], где [math]Ends_{a, b}(S)[/math] это число концов отрезков [math]S[/math], находящихся в пределах полосы [math]\langle a, b \rangle[/math].

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

Если точка [math]p[/math] отрезка [math]s[/math] лежит между ступеньками [math]i[/math] и [math]i + 1[/math], тогда число [math]i[/math] называется местоположением [math]s[/math] на лестнице [math]D[/math] и обозначается как [math]Loc(D, s)[/math]

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

Имея лестницу [math]D = (Q, \langle a, b \rangle)[/math] и множество отрезков [math]S[/math], множество [math]Int(D, S)[/math] можно найти за время [math]O(|S| log|Q| + |Int(D, S)|)[/math]. Однако, если [math]S’[/math] упорядочено отношением [math]\lt _x[/math], где [math]x \in [a, b][/math], тогда можно найти [math]Int(D, S)[/math] за время [math]O(|S| + |Q| + |Int(D, S)|)[/math].

Алгоритм

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

Split

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

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

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

Search In Strip

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

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

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

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

Литература

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