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

Материал из Викиконспекты
Версия от 19:09, 25 сентября 2013; 194.85.161.2 (обсуждение) (Создание страницы)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

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

Примечания