触发Douglas-Peucker算法的Worst-Case的线？

Question

的道格拉斯-普克线简化算法具有O(N²)的最坏情况下的时间复杂度.然而,对于实际触发这种最坏情况的一条线,两件事必须立即"错误":

• 必须将阈值设置得如此之低以至于保留大多数顶点
• 在每个递归步骤中,与当前端点之间的线偏差最大的顶点必须与其中一个端点接近(就其在线上的索引而言,而不是在其欧氏位置方面).(如果相反,与线的偏差最大的顶点的索引足够接近当前端点之间的中间,则算法应该导致深度的递归二进制细分log(n),从而导致总体时间复杂度O(n log(n)).)

虽然第一个标准很容易触发(只是将公差阈值设置为0.0),但我还没有找到满足第二个标准的线.

那么是否存在导致最坏情况行为的简单示例行(最好是触发明显最坏情况的行为,其中每个递归步骤中具有最高偏差的点直接连接到行的一个端点;但是任何其他示例还好吗？

Answer 1

所以Vincent van der Weele似乎是正确的,一个增加幅度的简单曲折线将触发Douglas-Peucker算法的O(n²)最坏情况:

在这种情况下,距离连接两个端点的线的距离最长的顶点将始终是与右侧端点直接相邻的顶点.因此,Douglas-Peucker算法在这里需要O(n)细分步骤,其中每个步骤只刮削最右边的顶点,因此需要迭代剩余的O(n)顶点以找到距离最长的那个 - 给出一个O(n²)的总时间复杂度