Алгоритм Балабана — различия между версиями
(→Литература) |
|||
| Строка 5: | Строка 5: | ||
==Введение== | ==Введение== | ||
| − | Методы поиска пересечений отрезков разделяются на детерминированные и недетерминированные. Тривиальный детерминированный алгоритм имеет временную сложность <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.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> памяти. | + | Методы поиска пересечений отрезков разделяются на детерминированные и недетерминированные. Тривиальный детерминированный алгоритм имеет временную сложность <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://booksshare.net/books/math/preparata-f/1989/files/vichgeometr.pdf ''Ф.Препарата, М.Шеймос {{---}} Вычислительная геометрия (стр. 348 - 350)'']</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> памяти. | ||
==Алгоритм== | ==Алгоритм== | ||
Версия 14:20, 26 сентября 2013
Алгоритм Балабана — детерминированный алгоритм, позволяющий по множеству отрезков на плоскости получить множество точек, в которых эти отрезки пересекаются
Содержание
Введение
Методы поиска пересечений отрезков разделяются на детерминированные и недетерминированные. Тривиальный детерминированный алгоритм имеет временную сложность и суть его заключается в проверке попарного пересечения отрезков.
Сложнее, но эффективнее алгоритм Бентли-Отмена [1] с оценкой сложности , в основе которого лежит метод заметающей прямой.
Алгоритм, предложенный Чазеле и Едельсбруннером [2], имеет лучшую оценку , но в отличие от предыдущих методов требует квадратичной памяти.
Оптимальный детерминированный алгоритм был предложен Балабаном [3] с временной оценкой сложности и памяти.
Алгоритм
Примечания
Литература
Т.Вознюк, В.Терещенко — К построению эффективного решения задачи пересечения отрезков
Ф.Препарата, М.Шеймос — Вычислительная геометрия
