Clever Geek Handbook

The line that triggers the worst case for the Douglas-Puker algorithm?

the Douglas-Picker line simplification algorithm has the worst time complexity O (n²). However, in order for the line to actually trigger this worst case, two things had to go "wrong" at once:

  • the threshold should be set so low that most vertices are preserved.
  • at each stage of the recursion, the vertex with the greatest deviation from the line between the current endpoints must be close (by the index on the line, not by its Euclidean position) to one of the endpoints. (If, instead, the index of the vertex with the greatest deviation from the line was close enough to the midpoint between the current endpoints, the algorithm should invoke recursive binary depth splitting log(n)

    , resulting in a total time complexity O(n log(n))

    .)

While the first criterion is easy to call (just set the tolerance threshold to 0.0), I haven't yet found a line that fulfills the second criterion.

So, is there a simple example line that leads to the worst behavior (preferably one that triggers the obvious worst case, where the point with the highest deviation at each stage of the recursion is directly related to one of the line endpoints, but any other example is also good)?

+3


source to share


1 answer


So Vincent van der Veele seems to be right, a simple zigzag line with increasing amplitude will cause a worst-case O (n²) for the Douglas-Pucker algorithm:

enter image description here



In this case, the vertex with the longest distance from the line connecting the two endpoints will always be the one directly next to the endpoint on the right. Thus, the Douglas-Puker algorithm here requires O (n) partitioning steps, where each step simply shaves the right vertex and therefore has to iterate over the remaining O (n) vertices to find the one with the greatest distance - giving the total time complexity O (n²)

+4


source






More articles:


All Articles