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

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

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

Введение

Решение задачи по поиску множества пересечений отрезков является одной из главных задач вычислительной геометрии. Тривиальный детерминированный алгоритм имеет временную сложность [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]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].

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

Литература

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