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

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

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

Введение

Решение задачи по поиску множества пересечений отрезков является одной из главных задач вычислительной геометрии. Тривиальный детерминированный алгоритм имеет временную сложность [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 b, e \rangle[/math] обозначим вертикальную полосу, которая ограничена прямыми [math]x = b[/math] и [math]x = e[/math], а через [math]s[/math] отрезок с концами абсцисс [math]l[/math] и [math]r[/math].
Рассмотрим взаимное расположение вертикальной полосы [math]\langle b, e \rangle[/math] и отрезка [math]s[/math].

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

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

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

- пересекает(cross) полосу в других случаях.

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