カークパトリック・ザイデルアルゴリズム

カークパトリック・ザイデルアルゴリズムは、その著者らによって「究極の平面凸包アルゴリズム」として提案され、平面上の点の集合の凸包を計算するアルゴリズムであり、計算時間はである。ここで、 は入力点の数、 は包内の点（一部の文献では非支配点または最大点と呼ばれる）の数である。したがって、このアルゴリズムは出力に敏感である。つまり、実行時間は入力サイズと出力サイズの両方に依存する。別の出力に敏感なアルゴリズムであるギフトラッピングアルゴリズムは、かなり以前から知られていたが、カークパトリック・ザイデルアルゴリズムの漸近的実行時間は大幅に短く、常に出力に敏感でないアルゴリズムの限界を超えている。カークパトリック・ザイデルアルゴリズムは、その発明者であるデビッド・G・カークパトリックとライムンド・ザイデルにちなんで名付けられた。^[1]${\displaystyle {\mathcal {O}}(n\log h)}$ ${\displaystyle n}$${\displaystyle h}$${\displaystyle {\mathcal {O}}(n\log n)}$

このアルゴリズムは漸近的には最適だが、中規模の問題にはあまり実用的ではない。^[2]

このアルゴリズムの基本的な考え方は、 Preparataと Hongの凸包に対する分割統治アルゴリズムの一種の逆であり、著者らはこれを「征服前の結婚」と呼んでいます。

従来の分割統治アルゴリズムでは、入力ポイントを垂直線などで 2 つの等しい部分に分割し、入力の左側と右側のサブセットの凸包を再帰的に見つけ、次に 2 つの包を上下か​​ら接続する「ブリッジ エッジ」、つまり接線を見つけることで 2 つの包を 1 つに結合します。

カークパトリック・ザイデルアルゴリズムは、入力点のx座標の中央値を見つけることによって、前と同じように入力を分割します。ただし、このアルゴリズムでは後続のステップの順序が逆になっています。次のステップでは、この中央x座標によって定義される垂直線と交差する凸包のエッジを見つけますが、これには線形時間が必要であることがわかります。^[3]分割線の左側と右側にある、最終的な包に寄与できないポイントは破棄され、アルゴリズムは残りのポイントに対して再帰的に処理を進めます。より詳細には、アルゴリズムは凸包の上部と下部に対して別々の再帰を実行します。上部包の再帰では、破棄される寄与しないポイントは垂直方向に橋のエッジより下にあるポイントであり、下部包の再帰では、垂直方向に橋のエッジより上にあるポイントが破棄されます。

再帰の 番目のレベルでは、アルゴリズムは最大 個のサブ問題を解きます。各サブ問題は新しい凸包エッジを見つけるため、考慮されるサブ問題の総数は最大 個です。最悪のケースは、破棄できるポイントがなく、サブ問題が可能な限り大きい場合、つまり、レベル までの各再帰レベルにちょうど 個のサブ問題がある場合です。この最悪のケースでは、再帰のレベルがあり、各レベル内で考慮されるポイントがあるため、合計実行時間は前述のとおりです。 ${\displaystyle i}$${\displaystyle 2^{i}}$${\displaystyle {\frac {n}{2^{i}}}}$${\displaystyle h}$${\displaystyle 2^{i}}$${\displaystyle \log_{2}h}$${\displaystyle {\mathcal {O}}(\log h)}$${\displaystyle {\mathcal {O}}(n)}$${\displaystyle {\mathcal {O}}(n\log h)}$

• 凸包アルゴリズム