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