Loading article…
カークパトリック・ザイデルアルゴリズムは、平面上の点の集合の凸包を計算するために設計されたアルゴリズムであり、時間計算量は、 どこは入力点の数であり、は凸包上の点の数です。[ 1 ]この出力依存の時間計算量は、アルゴリズムの実行時間が入力サイズと出力サイズの両方に依存することを意味します。
ギフトラッピングアルゴリズムなどの以前の出力重視アルゴリズムは、漸近実行時間が一方、出力に依存しないアルゴリズムは通常、時間。カークパトリック・ザイデルアルゴリズムは、より効率的な漸近的限界を達成することで大幅な改善をもたらし、特定の種類の入力に対してより高速になります。
理論的には最適であるにもかかわらず、このアルゴリズムは実装の複雑さと漸近表記に隠された定数のために、中規模のデータセットに対しては実際には広く使用されていない。[ 2 ]
カークパトリック・ザイデルアルゴリズムは、凸包を計算するための古典的な分割統治法を改良したもので、しばしば「征服前の結婚」と表現されます。従来の分割統治法では、点の集合を（通常は垂直線で）2つの半分に分割し、それぞれの半分の凸包を再帰的に計算し、それらを接続する「橋」となる辺（二重接線）を見つけることで2つの凸包を結合します。
対照的に、Kirkpatrick–Seidel アルゴリズムは、まず点のメディアンを求めます。-座標を取得し、この中央値で垂直線と交差する凸包のエッジを特定します。[ 3 ]中央線の両側で凸包に寄与できない点は破棄されます。次に、アルゴリズムは残りの点に対して再帰的に進み、凸包の上部と下部を計算します。
各再帰レベルでアルゴリズムは最大でサブ問題、それぞれ最大でポイント。各部分問題は凸包の単一のエッジを特定するため、部分問題の総数は、、これはハル上の点の数です。最悪の場合、早期に破棄できる点がない場合、再帰の深さは、各レベルのプロセスポイント。これにより、全体の時間計算量は。
カークパトリック・ザイデルアルゴリズムは、その導入以来、凸包アルゴリズムの理論的側面と実践的側面の両方において、数々の発展を促してきた。特に、近年の進歩は、インスタンス最適性と普遍的最適性に焦点を当てている。
インスタンス最適性：この概念は、入力点の分布と形状に基づいて、特定のインスタンスセットに最適なアルゴリズムを見つけることに関連しています。最近の研究では、特定の入力分布に適応し、典型的なデータセットでのパフォーマンスを動的に向上させるアルゴリズムが検討されています。[ 4 ]
普遍的最適性：この開発では、あらゆる種類の入力に対して最適なアルゴリズムを追求し、幅広い入力構成において最悪ケースのパフォーマンスを保証することを目指します。カークパトリック・ザイデルアルゴリズムは、2次元凸包における普遍的最適性の有力な候補です。
量子アプローチ：量子コンピューティングの台頭に伴い、凸包に対する量子アルゴリズムの研究が行われており、特定のケースにおいて量子アルゴリズムがキルクパトリック・ザイデルアルゴリズムなどの古典的な手法を上回ることができるかどうかが検討されている。しかし、量子による高速化は依然として未解決の研究分野である。[ 5 ]
Kirkpatrick–Seidel アルゴリズムは理論的には時間計算量の観点から最適ですが、いくつかの要因により、中規模のデータセットに対する実用性は限られています。 McQueen と Toussaint の実験的研究[ 6 ]では、このアルゴリズムは大規模なデータセットではうまく機能するものの、漸近表記に隠された定数係数により、Chanのアルゴリズムなど他のアルゴリズムと比較すると、小規模なインスタンスでは効率が悪くなります。[ 7 ] Chanのアルゴリズムは、理論的には漸近的に効率が劣りますが、実装が簡単で小規模なインスタンスでのパフォーマンスが優れているため、実際には好まれることが多いです。
Chanのアルゴリズムなどの他の出力依存型凸包アルゴリズムと比較すると、Kirkpatrick–Seidelアルゴリズムはより優れた漸近的境界を提供します（対ギフトラッピングアルゴリズムとチャンの方法については、チャンの方法がある。しかし、チャンのアルゴリズムは実装が簡単で、定数係数が小さく、幅広い実用的なデータセットでのパフォーマンスが優れているため、より実用的である。中規模の問題では、特に実装が容易で定数係数が優れているため、チャンのアルゴリズムは依然として人気のある選択肢である。[ 8 ]
キルクパトリック・ザイデルアルゴリズムは理論的には最適であるものの、その実用的応用と理論的拡張の両方において、いくつかの未解決の問題が残っている。
実装の複雑さ：このアルゴリズムは複雑な再帰構造を持ち、点のメディアンを求めることに依存しているため、特に設計がより単純な他のアルゴリズムと比較すると、効率的に実装するのが難しくなります。
定数因子：時間計算量における隠れた定数中規模のデータセットの場合、実際にはアルゴリズムの処理速度が低下し、実用性が制限される可能性がある。
高次元への一般化：このアルゴリズムは2次元では効率的ですが、高次元空間における凸包問題の複雑さが増すため、高次元への一般化には大きな課題が伴います。
量子アルゴリズム：凸包計算の高速化を実現する量子アルゴリズムの可能性は、活発な研究分野である。しかし、実用的なシナリオにおいて、Kirkpatrick–Seidel のような古典的なアルゴリズムを上回る量子アルゴリズムはまだ証明されていない。[ 9 ]
