Content deleted Content added
Citation bot (talk | contribs) Add: s2cid. | Use this bot. Report bugs. | #UCB_CommandLine |
add O(n) version of the algorithm |
||
Line 65:
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>
Under certain circumstances, the complexity can be reduced to {{math|''O''(''n'')}} using an iterative approach.<ref>https://gist.github.com/stohrendorf/aea5464b1a242adca8822f2fe8da6612</ref>
==Similar algorithms==
| |||