Douglas-Peucker ライン単純化アルゴリズムの最悪の場合の時間計算量は O(n²) です。ただし、この最悪のケースを実際にトリガーする行については、次の 2 つのことが同時に「うまくいかない」必要があります。
- ほとんどの頂点が保持されるように、しきい値を非常に低く設定する必要があります
- 各再帰ステップで、現在の端点間の線からの偏差が最大の頂点は、端点の 1 つに (ユークリッド位置ではなく、線上のインデックスの点で) 近くなければなりません。(代わりに、線からの最大の偏差を持つ頂点のインデックスが現在の端点の中間に十分近い場合、アルゴリズムは深さ の再帰的なバイナリ細分割を引き起こし
log(n)、全体的な時間の複雑さは になりO(n log(n))ます。)
最初の基準は簡単にトリガーできますが (許容しきい値を 0.0 に設定するだけです)、2 番目の基準を満たす線はまだ見つかりません。
したがって、最悪のケースの動作をもたらす簡単な例の行があります(できれば、各再帰ステップで最大の偏差を持つポイントが行のエンドポイントの1つに直接接続されるという明らかな最悪のケースをトリガーするものです;しかし、他の例も大丈夫です）？
