Line that triggers Worst-Case for Douglas-Peucker Algorithm?

Question

The Douglas-Peucker line simplification algorithm has a worst-case time complexity of O(n²). However, for a line to actually trigger this worst-case, two things have to go "wrong" at once:

• the threshold must be set so low that most vertices are kept
• in each recursion step, the vertex with the largest deviation from the line between the current endpoints must be close (in terms of its index on the line, not in terms of its euclidean position) to one of the endpoints. (If instead the index of the vertex with the largest deviation from the line was close enough to the middle between the current endpoints, the algorithm should cause a recursive binary subdivision of depth log(n), resulting in an overall time complexity of O(n log(n)) .)

While the first criterion is easy to trigger (just set the tolerance threshold to 0.0), I have not yet found a line that fulfils the second criterion.

So is there a simple example line that results in the worst-case behavior (preferably one that triggers the obvious worst-case where the point with the highest deviation in each recursion step is directly connected to one of the line's endpoints; but any other example is fine as well)?

Answer 1

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

In this case, the vertex with the longest distance from the line connecting the two endpoints will always be the one directly adjacent to the endpoint on the right. Thus, the Douglas-Peucker algorithm will here require O(n) subdivision steps, where each step just shaves of the rightmost vertex and thus needs to iterate over the remaining O(n) vertices to find the one with the longest distance - giving a total time complexity of O(n²)