爲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²）