触发Douglas-Peucker算法最坏情况的线是什么？

Question

道格拉斯-普克(Douglas-Peucker)折线简化算法的最坏时间复杂度为O(n²)。然而，要使一条线真正触发这种最坏情况，必须同时出现两件事情：

• 阈值必须设置得非常低，以保留大部分顶点。
• 在每个递归步骤中，离当前端点连线的偏差最大的顶点必须靠近（按照其在线上的索引而不是欧几里德位置）其中一个端点。如果离线段的最大偏差点的索引足够靠近当前端点之间的中心，则算法应该会导致深度为log(n)的递归二进制细分，从而导致总时间复杂度为O(n log(n))。

尽管第一个标准很容易触发（只需将容限阈值设置为0.0），但我还没有找到一条符合第二个标准的线。

那么，是否存在一个简单的示例线路可以产生最坏情况（最好是触发每个递归步骤中偏差最大的点直接连接到线路端点的显而易见的最坏情况；但是任何其他示例也可以）？

- Dreamer

---

一些“之字形”的图案可能会有所帮助。例如，考虑一些具有x位置 [0, 1, ..., 10] 和y位置 [0, 10, -9, 8, ..., 0] 的点。当你画出来时，更容易看到它的效果 ;) - Vincent van der Weele

Answer 1

所以Vincent van der Weele似乎是正确的，一个简单的波浪线，振幅逐渐增加，将触发Douglas-Peucker算法的O(n²)最坏情况：

在这种情况下，距离连接两个端点的直线最远的顶点将始终是直接相邻于右端点的顶点。因此，Douglas-Peucker算法在这里需要O(n)的子分割步骤，每个步骤只需刮掉最右侧的顶点，因此需要遍历其余O(n)个顶点以找到具有最长距离的顶点 - 总时间复杂度为O(n²)。

- Dreamer