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

Материал из Викиконспекты
Перейти к: навигация, поиск
Эта статья находится в разработке!

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

Введение

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

Алгоритм

Примечания

Литература