Content deleted Content added
Citation bot (talk | contribs) Altered pages. Formatted dashes. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Computer graphics algorithms | #UCB_Category 33/49 |
→Similar algorithms: Added Imai-Iri (after Hiroshi Imai and Masao Iri) |
||
| (One intermediate revision by one other user not shown) | |||
Line 60:
== 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 yields a running time of {{math|''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 yields a running time of {{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'')}} 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>
Line 76:
* Lang simplification
* Zhao–Saalfeld
* Imai-Iri
== See also ==
| |||