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

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

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

Литература

К построению эффективного решения задачи пересечения отрезков