Douglas-Peucker line simplification algorithm最坏情况下的时间复杂度为 O(n²)。然而，对于一条真正触发这种最坏情况的线路，有两件事必须同时“出错”:
- 必须将阈值设置得如此低，以便保留大多数顶点
- 在每个递归步骤中，与当前端点之间的直线偏差最大的顶点必须接近(根据它在直线上的索引，而不是根据它的欧氏位置)到端点之一。 (相反，如果与线的偏差最大的顶点的索引足够接近当前端点之间的中间，则该算法应该导致深度
log(n)的递归二进制分割，从而导致O(n log(n))的总体时间复杂度。)
虽然第一个条件很容易触发(只需将容差阈值设置为0.0)，但我还没有找到满足第二个条件的线。
那么是否有一条导致最坏情况行为的简单示例线(最好是触发明显最坏情况的线，其中每个递归步骤中偏差最大的点直接连接到线的端点之一；但是任何其他示例也可以)？
最佳答案
所以 Vincent van der Weele 似乎是正确的，一条简单的锯齿形线随着幅度的增加将触发 Douglas-Peucker 算法的 O(n²) 最坏情况:
在这种情况下，与连接两个端点的直线距离最长的顶点将始终是与右侧端点直接相邻的顶点。因此，Douglas-Peucker 算法在这里需要 O(n) 次分割步骤，其中每个步骤仅剃除最右边的顶点，因此需要迭代剩余的 O(n) 个顶点以找到距离最长的顶点 - 给出O(n²) 的总时间复杂度
关于algorithm - 触发道格拉斯-普克算法最坏情况的线？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31516058/