Изменения
→Обзор ускорения работы алгоритма Дугласа-Пекера
Как описано выше, в худшем случае алгоритм работает за <tex>O(n^2)</tex>. Можно внести дополнения, которые позволят получить <tex>O(n\log n)</tex> в худшем случае. Ускорение основывается на уменьшении времени поиска наиболее удаленной вершины. Это можно осуществить благодаря идее о том, что наиболее удаленная вершина лежит на выпуклой оболочке полигональной цепи. Описание ускорения взято из статьи Хершберга(Hershberger) ''[http://www.bowdoin.edu/~ltoma/teaching/cs350/spring06/Lecture-Handouts/hershberger92speeding.pdf Speeding Up the Douglas-Peucker Line-Simplification Algorithm]'' (1992).
Для построения выпуклой оболочки используется [http://www.ams.sunysb.edu/~jsbm/courses/545/melkman.pdf алгоритм Мелкмана], который работает для двумерной полигональной цепи без самопересечений за <tex>O(n)</tex>, строя все промежуточные выпуклые оболочки, которые пригодятся в дальнейшем.
Построив выпуклую оболочку, используется бинарный поиск для нахождения наиболее удаленной вершины за <tex>O(\log n)</tex>. Затем, если потребуется, действия повторятся рекурсивно, как и в оригинальном алгоритме, но заново строить оболочки не имеет смысла, так как промежуточные уже были построены. Использовав их, можно разбить текущую оболочку на две за <tex>O(\log n)</tex>.
