Изменения

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

Методы поиска пересечений отрезков разделяются на детерминированные и недетерминированные. Тривиальный детерминированный алгоритм имеет временную сложность <tex>O(n2n^2)</tex> и суть его заключается в проверке попарного пересечения отрезков. Сложнее, но эффективнее алгоритм Бентли-Отмена <ref>[2http://neerc.ifmo.ru/wiki/index.php?Алгоритм_Бентли-Оттмана ''Алгоритм_Бентли-Оттмана''] </ref> с оценкой сложности <tex>O((n+k)logn\ log(n)+k)</tex>, в основе которого лежит метод заметающей прямой. Алгоритм, предложенный Чазеле и Едельсбруннером [3], имеет лучшую оценку <tex>O(n log n + k)</tex>, но в отличие от предыдущих методов требует квадратичной памяти. Оптимальный детерминированный алгоритм был предложен Балабаном <ref>{{книга|автор = [http://www.cs.sfu.ca/~binay/813.2011/Balaban.pdf ''I.J. Balaban.|заглавие = An optimal algorithm for finding segments intersections|издательство = . In Proceedings of the Eleventh Annual Symposium on Computational Geometry, ACM Press|место = М, New York, 1995.|год = 1995|страниц = - pp. 211–219}}.'']</ref> с временной оценкой сложности <tex>O(n \ log (n) + k)</tex> и <tex>O(n)</tex> памяти.

{{примечания}}==Литература== [http://www.graphicon.ru/proceedings/2010/conference/RU/Se4/021.pdf ''К построению эффективного решения задачи пересечения отрезков'']<br>