Revision as of 12:30, 5 August 2024 edit Kenneth Kho (talk \| contribs) Extended confirmed users 1,512 edits mNo edit summary ← Previous edit		Revision as of 13:28, 7 August 2024 edit undo Kenneth Kho (talk \| contribs) Extended confirmed users 1,512 edits Added {{math\|''O''(''n''<sup>3</sup>)}} complexity for DEM generalization using the 3D algorithm Next edit →
Line 63: == Complexity == The running time of this algorithm when run on a polyline consisting of {{math\|''n'' – 1}} segments and {{mvar\|n}} vertices is given by the recurrence {{math\|''T''(''n'') {{=}} ''T''(''i'' + 1) + ''T''(''n'' − ''i'') + [[Big O notation\|''O''(''n'')]]}} where {{math\|''i'' {{=}} 1, 2,..., ''n'' − 2}} is the value of <code>index</code> in the pseudocode. In the worst case, {{math\|''i'' {{=}} 1}} or {{math\|''i'' {{=}} ''n'' − 2}} at each recursive invocation and this algorithm has a running time of {{math~~\|[[Big theta~~\|''ΘO''(''n''<sup>2</sup>)]]}}. In the best case {{math\|''i'' {{=}} {{sfrac\|''n''\|2}}}} or {{math\|''i'' {{=}} {{sfrac\|''n'' ± 1\|2}}}} 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'')}}. Using (fully or semi-) [[dynamic convex hull]] data structures, the simplification performed by the algorithm can be accomplished in {{math\|''O''(''n'' log ''n'')}} time.<ref>{{cite tech report \|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> Given specific conditions related to the bounding metric, it is possible to decrease the computational complexity to a range between {{math\|''O''(''n'')}} and {{math\|''O''(''2n'')}} through the application of an iterative method.<ref>{{Cite web\|url=https://gist.github.com/stohrendorf/aea5464b1a242adca8822f2fe8da6612\|title=ramer_douglas_peucker_funneling.py\|website=Gist}}</ref> The running time for [[digital elevation model]] generalization using the three-dimensional variant of the algorithm is {{math\|''O''(''n''<sup>3</sup>)}}, but techniques have been developed to reduce the running time for larger data in practice.<ref>{{cite journal \|last1=Fei \|first1=Lifan \|last2=He \|first2=Jin \|title=A three-dimensional Douglas–Peucker algorithm and its application to automated generalization of DEMs \|journal=International Journal of Geographical Information Science \|date=2009 \|volume=23 \|issue=6 \|pages=703-718 \|doi=10.1080/13658810701703001}}</ref> ==Similar algorithms==

Ramer–Douglas–Peucker algorithm: Difference between revisions