为Douglas-Peucker算法触发最坏情况的行？

Question

Douglas-Peucker line simplification algorithm的最坏情况时间复杂度为O（n²）。然而，对于一个线实际上触发这种最坏的情况下，两件事情必须去“错误”的一次：

• 门槛必须每个递归步骤设置如此之低，最顶点保持
• ，与当前端点之间的直线偏离最大的顶点必须靠近其中一个端点（根据其在线上的索引，而不是欧几里得位置）。 （如果相反，与线偏离最大的顶点的索引足够接近当前端点之间的中间值，则该算法应导致深度为log(n)的递归二进制细分，从而导致整体时间复杂度为O(n log(n))。）

虽然第一个标准很容易触发（只需将公差阈值设置为0.0），但我还没有找到满足第二个标准的线条。因此，是否存在导致最坏情况行为的简单示例行（最好是触发最明显的最差情况，即每个递归步骤中具有最高偏差的点直接连接到行的一个端点;但其他任何例子都很好）？

Answer 1

所以文森特·范德Weele似乎是正确的，随着振幅将触发O（N²）最坏情况的道格拉斯 - 普克算法简单的锯齿线：

在这种情况下，与连接两个端点的线距离最远的顶点将始终是与右端端点直接相邻的顶点。因此，Douglas-Peucker算法在这里需要O（n）个细分步骤，其中每个步骤只是对最右边的顶点进行修剪，因此需要遍历剩余的O（n）个顶点以找到距离最长的一个 - 给出总时间复杂度为O（n²）