304
правки
Изменения
Нет описания правки
===Время работы===
Ожидаемая сложность алгоритма может быть оценена выражением <tex>\Theta(n\log n)</tex> в лучшем случае, когда номер наиболее удаленной точки всегда оказывается лексикографически центральным. Однако в худшем случае сложность алгоритма <tex>O\left(n^2\right)</tex>, когда номер наиболее удаленной точки всегда соседний к номеру граничащей точки.
===Замечания к алгоритму===
==Обзор ускорения работы алгоритма Дугласа-Пекера==
Как описано выше, в худшем случае алгоритм работает за <tex>O\left(n^2\right)</tex>. Можно внести дополнения, которые позволят получить <tex>O\left(n\log n\right)</tex> в худшем случае. Ускорение основывается на уменьшении времени поиска наиболее удаленной вершины. Это можно осуществить благодаря идее о том, что наиболее удаленная вершина лежит на выпуклой оболочке полигональной цепи.
Для построения выпуклой оболочки используется алгоритм Мелкмана, который работает для двумерной полигональной цепи без самопересечений за <tex>O(n)</tex>, строя все промежуточные выпуклые оболочки, которые пригодятся в дальнейшем.
Построив выпуклую оболочку, используется бинарный поиск для нахождения наиболее удаленной вершины за <tex>O(\log n)</tex>. Затем, если потребуется, действия повторятся рекурсивно, как и в оригинальном алгоритме, но заново строить оболочки не имеет смысла, так как промежуточные уже были построены. Использовав их, можно разбить текущую оболочку на две за <tex>O(\log n)</tex>.
В итоге получается <tex>O\left(n\right)</tex> разбиений за <tex>O\left(\log n\right)</tex> и поиск за <tex>O\left(\log n\right)</tex> в худшем случае, что дает <tex>O\left(n\log n\right)</tex>.
===Замечания===
К сожалению, у данного метода есть несколько недостатков по сравнению с оригинальным алгоритмом, некоторые из которых уже были упомянуты:
