Изменения

Алгоритм может находить не минимальный по количеству точек ответ. Рассмотрим пример, где исходная линия с некоторым приближением будет представлять полуокружность. Мы можем подобрать такое <tex>\varepsilon</tex>, что алгоритм добавит три точки помимо стартовой и конечной (точки через каждую четверть исходной линии), в то же время мы можем взять две точки через

каждую треть исходной линии, для которых упрощение также верно.

<br clear="all">

*Оба предыдущих условия ложны, то <tex>abs(| \overrightarrow{R_{12}} \times \overrightarrow{R_1}|/|\overrightarrow{R_{12}}|)</tex>, где <tex> \overrightarrow{R_{12}} = (x_2 -x_1, y_2 - y_1)</tex> и <tex> \overrightarrow{R_1} = (x_1 - x_0, y_1 - y_0)</tex>. Это следует из формул для площади параллелограмма через векторное произведение и через произведения основания на высоту

==Обзор ускорения работы алгоритма Дугласа-Пекера==

Как описано выше, в худшем случае алгоритм работает за <tex>O(n^2)</tex>. Можно внести дополнения, которые позволят получить <tex>O(n\log n)</tex> в худшем случае. Ускорение основывается на уменьшении времени поиска наиболее удаленной вершины. Это можно осуществить благодаря идее о том, что наиболее удаленная вершина лежит на выпуклой оболочке полигональной цепи.