Алгоритм Балабана — различия между версиями
(Создание страницы) |
(Добавление ссылок) |
||
| Строка 1: | Строка 1: | ||
| − | '''Алгоритм Балабана''' довольно таки интересный алгоритм, который мне еще предстоит реализовать, посему скидываю сюда все, что мне удастся найти, а потом нормально расставлю. | + | '''Алгоритм Балабана''' довольно таки интересный алгоритм, который мне еще предстоит реализовать, посему скидываю сюда все, что мне удастся найти, а потом все нормально расставлю. |
| − | Методы поиска пересечений отрезков разделяются на детерминированные и недетерминированные. Тривиальный детерминированный алгоритм имеет временную сложность <tex>O( | + | Методы поиска пересечений отрезков разделяются на детерминированные и недетерминированные. Тривиальный детерминированный алгоритм имеет временную сложность <tex>O(n^2)</tex> и суть его заключается в проверке попарного пересечения отрезков. Сложнее, но эффективнее алгоритм Бентли-Отмена <ref>[http://neerc.ifmo.ru/wiki/index.php?Алгоритм_Бентли-Оттмана ''Алгоритм_Бентли-Оттмана'']</ref> с оценкой сложности <tex>O((n + k)\ 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> памяти. |
| − | <ref> | ||
==Примечания== | ==Примечания== | ||
<references/> | <references/> | ||
| − | + | ||
| + | ==Литература== | ||
| + | |||
| + | [http://www.graphicon.ru/proceedings/2010/conference/RU/Se4/021.pdf ''К построению эффективного решения задачи пересечения отрезков'']<br> | ||
[[Категория: Вычислительная геометрия]] | [[Категория: Вычислительная геометрия]] | ||
Версия 19:26, 25 сентября 2013
Алгоритм Балабана довольно таки интересный алгоритм, который мне еще предстоит реализовать, посему скидываю сюда все, что мне удастся найти, а потом все нормально расставлю.
Методы поиска пересечений отрезков разделяются на детерминированные и недетерминированные. Тривиальный детерминированный алгоритм имеет временную сложность и суть его заключается в проверке попарного пересечения отрезков. Сложнее, но эффективнее алгоритм Бентли-Отмена [1] с оценкой сложности , в основе которого лежит метод заметающей прямой. Оптимальный детерминированный алгоритм был предложен Балабаном [2] с временной оценкой сложности и памяти.
Примечания
Литература
К построению эффективного решения задачи пересечения отрезков
