ギフトラッピングアルゴリズム

計算幾何学において、ギフトラッピング アルゴリズムは、与えられた点の 集合の凸包を計算するアルゴリズムです。

2 次元の場合、このアルゴリズムは1973 年にこのアルゴリズムを発表した RA Jarvis にちなんでJarvis 行進とも呼ばれます。計算時間はO ( nh )です。ここで、nは点の数、h は凸包上の点の数です。他の凸包アルゴリズムと比較した実際のパフォーマンスは、n が小さい場合、または h が n に対して非常に小さいと予想される場合に優れています^{[引用が必要]}。一般に、このアルゴリズムは他の多くのアルゴリズムよりもパフォーマンスが優れています (凸包アルゴリズムを参照)。

簡単にするために、以下の説明では、点が一般的な位置にある、つまり、どの 3 つの点も同一直線上にないことを前提としています。アルゴリズムは、 端点(凸包の頂点) のみを報告するか、凸包上にあるすべての点を報告するかの選択を含め、共線性に対処するように簡単に変更できます^{[要出典] 。また、完全な実装では、凸包に頂点が 1 つまたは 2 つしかない}退化したケースの処理方法、およびコンピューター計算と入力データの両方における 算術精度の制限の問題に対処する方法を選択する必要があります。

ギフトラッピングアルゴリズムは、i =0 と凸包上にあることがわかっている点p ₀ (たとえば、一番左の点) から始まり、すべての点が線p _i p _i+1の右側にあるように点p i +1 を選択します。この点は、極座標の中心として取られた点p _iに対するすべての点の極角を比較することによってO ( n ) 時間で見つけることができます。i = _i +1 とし、p _h = p ₀に達するまでを繰り返すと、 hステップで凸包が得られます。 2 次元では、ギフトラッピングアルゴリズムは、点の集合の周りに紐 (または包装紙) を巻き付けるプロセスに似ています。

このアプローチはより高い次元に拡張できます。

アルゴリズムjarvis(S)は
    // Sは点の集合である
    // P は凸包を形成する点の集合になります。最終的な集合のサイズは i です。
    pointOnHull := S の左端の点 // これは CH(S) の一部であることが保証されます
    私 := 0
    繰り返す
        P[i] := ポイントオンハル
        エンドポイント:= S[0] // ハル上の候補エッジの初期エンドポイント
        jが0から|S|までの場合、
            // エンドポイント == pointOnHull はまれなケースであり、j == 1 で、ループに適したエンドポイントがまだ設定されていない場合にのみ発生します。
            (endpoint == pointOnHull) または (S[j] が P[ i ] から endpoint までの線の左側にある)場合
                エンドポイント:= S[j] // 左折が大きいことがわかったので、エンドポイントを更新
        私 := 私 + 1
        pointOnHull := エンドポイント
    until endpoint == P[0] // 最初のハルポイントまで折り返します

内側のループは集合S内のすべての点をチェックし、外側のループは包上の各点に対して繰り返します。したがって、合計実行時間は です。実行時間は出力のサイズに依存するため、ジャービスの行進は出力に敏感なアルゴリズムです。 ${\displaystyle O(nh)}$

ただし、実行時間は包の頂点の数に 線形に依存するため、包の頂点の数hが log  nより小さい場合にのみ、グラハムスキャンなどのアルゴリズムよりも速くなります。別の凸包アルゴリズムであるChan のアルゴリズムは、グラハムスキャンの対数依存性とギフトラッピングアルゴリズムの出力感度を組み合わせ、グラハムスキャンとギフトラッピングの両方を改善する漸近的な実行時間を実現します 。 ${\displaystyle O(n\log n)}$${\displaystyle O(n\log h)}$

• 凸包アルゴリズム