Talk:Ramer–Douglas–Peucker algorithm: Difference between revisions

Revision as of 18:31, 7 December 2016

Revision as of 19:07, 10 December 2019

Line 32:

I just programmed that in AutoLisp and did not get any reduction until my head was wounded from scratching and I modified recResults2'''[1...end]''' to '''[2...end]''', which eliminates the point which is found with the index variable, similiar to the previously recResults1[1...end-1], which I think is the whole purpose of the recursive algorithm. Maybe a specialist can look into that. Please contact me, if this problem is solved or analyzed, my adress is abgang_at_ok.de. <!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/91.232.232.180|91.232.232.180]] ([[User talk:91.232.232.180#top|talk]]) 18:30, 7 December 2016 (UTC)</small> <!--Autosigned by SineBot-->

== Analysis ==

I just corrected the analysis section. The recurrence <math>T(n)=2T(n/2)+ O(n)</math> doesn't describe the average the running time of the algorithm under any reasonable interpretation of average-case. That particular recurrence does resolve to <math>\Theta(n\log n)</math> and the expected running-time of the algorithm is <math>\Theta(n\log n)</math> under some interpretations of average-case, though.