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

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

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

Введение

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

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

Будем говорить, что отрезок , с концами абсцисс и :

- содержит(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]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]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]Q[/math] содержит полосу [math]\langle a, b \rangle[/math];
− нет пересечений отрезков внутри лестницы;

− упорядочена по отношению .

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