Изменения
Создание страницы
'''Алгоритм Балабана''' довольно таки интересный алгоритм, который мне еще предстоит реализовать, посему скидываю сюда все, что мне удастся найти, а потом нормально расставлю.
Методы поиска пересечений отрезков разделяются на детерминированные и недетерминированные. Тривиальный детерминированный алгоритм имеет временную сложность <tex>O(n2)</tex> и суть его заключается в проверке попарного пересечения отрезков. Сложнее, но эффективнее алгоритм Бентли-Отмена [2] с оценкой сложности <tex>O((n+k)logn+k)</tex>, в основе которого лежит метод заметающей прямой. Алгоритм, предложенный Чазеле и Едельсбруннером [3], имеет лучшую оценку <tex>O(n log n + k)</tex>, но в отличие от предыдущих методов требует квадратичной памяти. Оптимальный детерминированный алгоритм был предложен Балабаном
<ref>{{книга|автор = I.J. Balaban.|заглавие = An optimal algorithm for finding segments intersections|издательство = ACM Press|место = М.|год = 1995|страниц = pp. 211–219}}</ref> с временной оценкой сложности <tex>O(n log (n) + k)</tex> и <tex>O(n)</tex> памяти.
==Примечания==
<references/>
{{примечания}}
[[Категория: Вычислительная геометрия]]
Методы поиска пересечений отрезков разделяются на детерминированные и недетерминированные. Тривиальный детерминированный алгоритм имеет временную сложность <tex>O(n2)</tex> и суть его заключается в проверке попарного пересечения отрезков. Сложнее, но эффективнее алгоритм Бентли-Отмена [2] с оценкой сложности <tex>O((n+k)logn+k)</tex>, в основе которого лежит метод заметающей прямой. Алгоритм, предложенный Чазеле и Едельсбруннером [3], имеет лучшую оценку <tex>O(n log n + k)</tex>, но в отличие от предыдущих методов требует квадратичной памяти. Оптимальный детерминированный алгоритм был предложен Балабаном
<ref>{{книга|автор = I.J. Balaban.|заглавие = An optimal algorithm for finding segments intersections|издательство = ACM Press|место = М.|год = 1995|страниц = pp. 211–219}}</ref> с временной оценкой сложности <tex>O(n log (n) + k)</tex> и <tex>O(n)</tex> памяти.
==Примечания==
<references/>
{{примечания}}
[[Категория: Вычислительная геометрия]]
