入力のすべての点が凸包上にある場合、quickhull アルゴリズムでパフォーマンスの低下を回避するにはどうすればよいですか?
質問する
1356 次
2 に答える
2
QuickHull のパフォーマンスは、主に、各再帰呼び出し (または反復) で入力の一部を破棄できることに起因します。残念ながら、すべての点が円上にある場合、これは起こりません。この場合でも、再帰呼び出しごとに分割ステップがかなりバランスの取れたパーティションを提供する場合、O(nlog n)最悪の場合のパフォーマンスを得ることが可能です。2 次実行時間になる最悪のケースは、各呼び出しで分割のバランスが著しく不均衡になった場合 (たとえば、1 つの分割が常に空になる場合) です。これはデータセットに大きく依存するため、できることはあまりありません。
代わりに、 Graham の scan の Andrew のバリアントやMergeHullなど、他のアルゴリズムを試してみることをお勧めします。両方とも、 O(nlog n)の最悪の場合の時間計算量が保証されています。
于 2012-05-05T07:32:26.810 に答える
0
いくつかのアルゴリズム実装の比較については、次のような多くの 2D アルゴリズムのパフォーマンスを比較する、高速で改善された 2D 凸包アルゴリズムと O(n log h) での実装に関する記事を参照することをお勧めします。
- モノトーンチェーン
- グラハムスキャン
- ドロネー/ボロノイ
- ちゃん
- リューとチェン
- ウエレット（私のもの）
于 2018-01-26T04:43:47.660 に答える