Revision as of 20:53, 4 December 2023 edit Dirkbb (talk \| contribs) Extended confirmed users 46,405 edits m Reverted 1 edit by 2804:214:8118:38CE:4475:C47B:DE32:9F78 (talk) to last revision by PhKindermann Tags: Twinkle Undo ← Previous edit		Revision as of 18:05, 27 May 2024 edit undo 2001:16b8:15c5:f200:e4f5:2442:3b7e:a8 (talk) refine complexity bounds for the iterative approach Next edit →
Line 66: 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~~Given ~~certain~~specific ~~circumstances~~conditions related to the bounding metric, it is possible to decrease the computational complexity ~~can~~to bea ~~reduced~~range tobetween {{math\|''O''(''n'')}} ~~using~~and {{math\|''O''(''2n'')}} through the application of an iterative ~~approach~~method.<ref>https://gist.github.com/stohrendorf/aea5464b1a242adca8822f2fe8da6612</ref> ==Similar algorithms==

Ramer–Douglas–Peucker algorithm: Difference between revisions