Изменения

'''Алгоритм Балабана''' {{---}} детерминированный алгоритм, позволяющий по множеству отрезков на плоскости получить множество точек, в которых эти отрезки пересекаются . <br>

Методы поиска Решение задачи по поиску множества пересечений отрезков разделяются на детерминированные и недетерминированныеявляется одной из главных задач вычислительной геометрии. Тривиальный детерминированный алгоритм имеет временную сложность <tex>O(n^2)</tex> , и его суть его заключается в проверке попарного пересечения отрезков.Сложнее, но эффективнее алгоритм Бентли-Оттмана <ref>[http://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_Бентли-Оттмана ''Алгоритм Бентли-Оттмана'']</ref> с оценкой сложности <tex>O((n + k)\ log(n)+k)</tex>, в основе которого лежит метод заметающей прямой.Алгоритм, предложенный Чазелле и Едельсбруннером <ref>[http://www.cs.princeton.edu/~chazelle/pubs/IntersectLineSegments.pdf ''An optimal algorithm for intersecting line segments in the plane'']</ref>, имеет лучшую оценку <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. - pp. 211–219.'']</ref> с временной оценкой сложности <tex>O(n\ log(n) + k)</tex> и <tex>O(n)</tex> памяти, где К - число пересекающихся отрезков. При количестве отрезков равным 2000 и большому количеству пересечений целесообразно использовать алгоритм Балабана. Однако в результате громоздкости и высокой сложности реализации алгоритма в большинстве практических задач используется алгоритм заметающей прямой Бентли-Оттмана.

Сложнее, но эффективнее алгоритм Бентли-Отмена <ref>[http://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_Бентли-Оттмана ''Алгоритм Бентли-Оттмана'']</ref> с оценкой сложности <tex>O((n + k)\ log(n)+k)</tex>, в основе которого лежит метод заметающей прямой.=Основные понятия==

АлгоритмВведем некоторые обозначения. Пусть <tex>Int(S)</tex> - множество всех точек пересечения отрезков из множества <tex>S</tex>, предложенный Чазеле и Едельсбруннером а <reftex>[http:K = |Int(S)|</tex> - количество таких пересечений ;<br>Через <tex>\langle b, e \rangle</booksshare.nettex> обозначим вертикальную полосу, которая ограничена прямыми <tex>x = b</bookstex> и <tex>x = e</mathtex>, а через <tex>s</preparata-ftex> отрезок с концами абсцисс <tex>l</1989tex> и <tex>r</files/vichgeometrtex>.pdf ''Ф.Препарата<br>Рассмотрим взаимное расположение вертикальной полосы <tex>\langle b, М.Шеймос {{---}} Вычислительная геометрия (стр. 348 - 350)'']e \rangle</reftex>, имеет лучшую оценку и отрезка <tex>O(n\ log(n) + k)s</tex>, но в отличие от предыдущих методов требует квадратичной памяти.

Оптимальный детерминированный алгоритм был предложен Балабаном {{Определение|definition=Будем говорить, что отрезок <reftex>[http:s</tex>, с концами абсцисс <tex>l</www.cs.sfu.catex> и <tex>r</~binaytex> : - '''содержит'''(span) полосу <tex>\langle b, e \rangle</813.2011tex>, если <tex>l \le b \le e \le r</Balaban.pdf tex>; <br>- '''внутренний'''I.J. Balaban. An optimal algorithm for finding segments intersections. In Proceedings of the Eleventh Annual Symposium on Computational Geometry(inner) для полосы <tex>\langle b, ACM Presse \rangle</tex>, New Yorkесли <tex>b < l < r < e</tex>; <br>- '''пересекает'''(cross) полосу <tex>\langle b, 1995e \rangle</tex> в других случаях. - pp. 211–219}} Два отрезка <tex>s_1</tex> и <tex>s_2</tex> называются пересекающимися внутри полосы <tex>\langle b, e \rangle</tex>, если их точка пересечения лежит в пределах этой полосы.<br>Для двух множеств отрезков <tex>S</tex> и <tex>S'']</reftex> с временной оценкой сложности определим множество <tex>OInt(n\ log(n) + kS, S')</tex> и как <tex>O\{ {s, s'} | (ns \in S, s' \in S') \& (s \ intersect \ s')\}</tex> памяти.