Ramer–Douglas–Peucker algorithm: Difference between revisions

Content deleted Content added
See also: per WP:SEEALSO, this section must not contain red links; reorganise accordingly
Complexity: MOS:REFPUNCT
Line 63:
The running time of this algorithm when run on a polyline consisting of <math>n-1</math> segments and <math>n</math> vertices is given by the recurrence <math>T(n)=T(i+1)+T(n-i) + O(n)</math> where <math>i\in\{1,\ldots,n-2\}</math> is the value of ''index'' in the pseudocode. In the worst case, <math>i=1</math> or <math>i=n-2</math> at each recursive invocation and this algorithm has a running time of <math>\Theta(n^2)</math>. In the best case <math>i=\lfloor n/2\rfloor</math> or <math>i=\lceil n/2\rceil</math> at each recursive invocation in which case the running time has the well-known solution (via the [[master theorem (analysis of algorithms)|master theorem for divide-and-conquer recurrences]]) of <math>O(n\log n)</math>.
 
Using (fully- or semi-)[[Dynamic convex hull]] data structures, the simplification performed by the algorithm can be accomplished in <math>O(n\log n)</math> time .<ref>{{cite techreport |last1 = Hershberger |first1 = John |first2 = Jack |last2 = Snoeyink |title = Speeding Up the Douglas-Peucker Line-Simplification Algorithm |date = 1992 | url = http://www.bowdoin.edu/~ltoma/teaching/cs350/spring06/Lecture-Handouts/hershberger92speeding.pdf}}</ref>.
 
==Similar algorithms==