Изменения

Пусть дано множество из <tex>n</tex> отрезков и требуется найти все точки их пересечения. Очевидно, что задачу можно решить полным перебором за <tex>O(n^2)</tex>; ясно также, что любой алгоритм будет в худшем случае работать за <tex>\Theta(n^2)</tex> (нетрудно привести пример, когда количество пересечений квадратично, а алгоритм обязан сообщить о каждом пересечении). Однако существуют алгоритмы, которые оптимальнее, если количество точек пересечения отрезков невелико. Так алгоритм Бентли-Оттмана (англ. Bentley-Ottmann) позволяет решить задачу о пересечении отрезков, используя <tex>O((n+I)\log{n})</tex> времени и <tex>O(n)</tex> памяти, где <tex>I</tex> {{---}} количество пересечений.