凸包アルゴリズム

さまざまなオブジェクトの凸包を構築するアルゴリズムは、数学やコンピュータサイエンスの分野で幅広く応用されています。

計算幾何学では、有限の点の集合の凸包を計算するためのアルゴリズムが数多く提案されており、計算の複雑さもさまざまです。

凸包を計算するということは、必要な凸形状の曖昧さのない効率的な表現が構築されることを意味します。対応するアルゴリズムの複雑さは、通常、入力ポイントの数nで推定されますが、凸包上のポイントの数 hで推定される場合もあります。

アルゴリズムへの入力が、直交平面上の有限の順序付けられていない点集合である一般的なケースを考えてみましょう。点が単純な多角形の境界を通過する順序で与えられる重要な特殊なケースについては、別のサブセクションで後述します。

すべての点が同じ線上にない場合、その凸包は、入力セット内のいくつかの点を頂点とする凸多角形になります。最も一般的な表現は、境界に沿って時計回りまたは反時計回りに並べられた頂点のリストです。一部のアプリケーションでは、凸多角形を半平面の集合の交差として表現すると便利です。

平面上の有限の点集合について、凸多角形として表される凸包を求める計算量の下限は、次の簡約法を使用してソートの場合と同じであることが簡単に示されます。ソートする数値集合について、平面上の点集合を考えます。それらは放物線、つまり凸曲線上にあるため、凸包の頂点を境界に沿って移動すると、数値のソート順序が生成されることは容易にわかります。明らかに、数値を点に変換し、そのソート順序を抽出するには、線形時間が必要です。したがって、一般的なケースでは、 n点の凸包をソートよりも速く計算することはできません。 ${\displaystyle x_{1},\dots ,x_{n}}$${\displaystyle (x_{1},x_{1}^{2}),\dots ,(x_{n},x_{n}^{2})}$${\displaystyle x_{1},\dots ,x_{n}}$

ソートの標準的な Ω( n log n ) 下限は、数値比較のみ実行でき、算術演算は実行できない計算の決定木モデルで証明されています。ただし、このモデルでは、凸包をまったく計算できません。また、ソートには、凸包に適した代数決定木モデルでも Ω( n log n ) 時間が必要であり、このモデルでは、凸包にも Ω( n log n ) 時間が必要です。^{[1]ただし、}整数ソートアルゴリズムを使用するなど、数値をO ( n log n ) 時間よりも速くソートできるコンピュータ演算モデルでは、平面凸包もより速く計算できます。凸包のグラハムスキャンアルゴリズムは、単一のソートステップと、それに続く線形量の追加作業で構成されます。

上で述べたように、入力サイズnの関数として凸包を見つける複雑さは、 Ω( n log n )によって下限が制限されます。ただし、一部の凸包アルゴリズムの複雑さは、入力サイズnと出力サイズh (包内の点の数)の両方で特徴付けることができます。このようなアルゴリズムは、出力に敏感なアルゴリズムと呼ばれます。h = o ( n )の場合、出力に敏感なアルゴリズムは、Θ( n log n ) アルゴリズムよりも漸近的に効率的である可能性があります。

出力に敏感な凸包アルゴリズムの最悪ケースの実行時間の下限は、平面の場合Ω( n log h ) と確立されています。 ^{[1]この最適な}時間計算量を達成するアルゴリズムはいくつかあります。最も古いものは、1986 年にKirkpatrickとSeidelによって導入されました (彼らはこれを「究極の凸包アルゴリズム」と呼びました)。1996 年にChanによってはるかに単純なアルゴリズムが開発され、Chan のアルゴリズムと呼ばれています。

既知の凸包アルゴリズムを、初版発行日順に以下に示します。各アルゴリズムの時間計算量は、入力点の数nと包上の点の数hで表されます。最悪の場合、h はnまで大きくなる可能性があることに注意してください。

• ギフトラッピング、別名ジャービスマーチ— O ( nh )
  最も単純な（ただし最悪の場合、最も時間効率が良いわけではない）平面アルゴリズムの 1 つです。1970 年に Chand と Kapur が、1973 年に RA Jarvis がそれぞれ独自に作成しました。時間計算量はO ( nh )、 nはセット内の点の数、 h は包内の点の数です。最悪の場合、計算量はO ( n ² ) です。
• グラハムスキャン— O ( n log n ) 1972 年にロナルド グラハム
  によって公開された、やや洗練されていますが、はるかに効率的なアルゴリズムです。ポイントがすでに座標の 1 つまたは固定ベクトルに対する角度によってソートされている場合、アルゴリズムには O( n ) の時間がかかります。
• クイックハル
  1977 年に W. Eddy によって、1978 年に A. Bykat によって独立して作成されました。クイックソートアルゴリズムと同様に、予想される時間計算量はO ( n log n ) ですが、最悪の場合にはO ( n ² )に悪化する可能性があります
• 分割統治法、別名マージハル— O ( n log n ) 1977 年にPreparata
  と Hong によって発表された別の O( n log n ) アルゴリズム。このアルゴリズムは 3 次元の場合にも適用できます。Chanはこれを「分割統治法のパラダイムの威力を示す最も優れた例の 1 つ」と呼んでいます。^[2]
• モノトーン チェーン、別名アンドリューのアルゴリズム— O ( n log n )
  1979 年に AM アンドリューによって公開されました。このアルゴリズムは、座標によって点を辞書式に並べ替えるグラハム スキャンのバリエーションと見ることができます。入力がすでに並べ替えられている場合、アルゴリズムにはO ( n ) の時間がかかります。
• 増分凸包アルゴリズム— O ( n log n )
  1984 年に Michael Kallay によって公開されました。
• カークパトリック・ザイデルアルゴリズム— O ( n log h )
  最初の最適な出力に敏感なアルゴリズム。これは、分割統治アルゴリズムを、結婚前の征服の手法と低次元線形計画法を使用して修正したものです。1986年にカークパトリックとザイデルによって公開されました
• Chan のアルゴリズム— O ( n log h ) 1996 年にChan
  によって作成された、より単純な最適な出力重視のアルゴリズムです。ギフトラッピングと、入力の小さなサブセットに対するO ( n log n ) アルゴリズム (Graham スキャンなど) の実行を組み合わせたものです。

次の単純なヒューリスティックは、凸包アルゴリズムの実装における最初のステップとして、パフォーマンスを向上させるためによく使用されます。これは、 1978 年にSelim AklとGT Toussaintが考案した効率的な凸包アルゴリズムに基づいています。その考え方は、凸包の一部にならない多くの点をすばやく除外することです。この方法は、次の考え方に基づいています。最低と最高の x 座標を持つ 2 つの点と、最低と最高の y 座標を持つ 2 つの点を検索します (これらの各操作にはO ( n ) かかります)。これらの 4 つの点は凸四辺形を形成し、この四辺形にあるすべての点 (最初に選択した 4 つの頂点を除く) は凸包の一部ではありません。この四辺形にあるすべての点を検索するのにも O( n ) かかるため、操作全体は O( n ) になります。オプションとして、x 座標と y 座標の合計が最小と最大の点、および x 座標と y 座標の差が最小と最大の点も四辺形に追加して、不規則な凸八角形を形成し、その内部を安全に破棄することができます。ポイントがランダム変数である場合、狭い範囲でよく見られる確率密度関数のクラスでは、この使い捨ての前処理ステップにより、凸包アルゴリズムの最悪ケースの複雑さがnの 2 乗であっても、凸包アルゴリズムは線形期待時間で実行されます。^[3]

上の議論は、すべての入力ポイントが事前にわかっている場合を想定しています。他の2つの設定も考えられます。^[1]

• オンライン凸包問題: 入力ポイントは 1 つずつ順番に取得されます。各ポイントが入力に到着した後、これまでに取得されたポイントセットの凸包を効率的に計算する必要があります。
• 動的凸包メンテナンス: 入力ポイントは順番に挿入または削除される可能性があり、挿入/削除操作のたびに凸包を更新する必要があります。

点の挿入により、凸包の頂点の数は最大 1 増加しますが、削除によりn頂点の凸包がn-1頂点の凸包に変換される場合があります。

オンラインバージョンは1ポイントあたりO(log n )で処理でき、漸近的に最適です。動的バージョンは1操作あたりO(log ² n )で処理できます。^[1]

単純な多角形の凸包は、多角形によって複数の部分に分割されます。そのうちの 1 つは多角形自体で、残りは多角形の境界の一部と単一の包のエッジによって囲まれたポケットです。単純な多角形の凸包を構築する問題に対して多くのアルゴリズムが公開されていますが、その約半分は間違っています。 ^[4] McCallum と Avis が最初の正しいアルゴリズムを提供しました。^[5] Graham & Yao (1983) と Lee (1983) による後の簡略化では、単一のスタック データ構造のみを使用します。彼らのアルゴリズムは、最も左の頂点から始めて、時計回りに多角形をトラバースします。その際、ポケット内にあることがまだ識別されていない頂点の凸シーケンスをスタックに格納します。各ステップで、アルゴリズムはスタック トップから、スタック トップに隣接する 2 つのポケットのいずれにも属さない次の頂点まで、多角形に沿ったパスをたどります。次に、スタックの一番上の2つの頂点とこの新しい頂点が凸位置にない間に、スタックをポップし、最後に新しい頂点をスタックにプッシュします。時計回りのトラバーサルが開始点に到達すると、アルゴリズムはスタックの頂点のシーケンスをハルとして返します。^{[6] [7]}

3次元の場合だけでなく、任意の次元の場合にも多くのアルゴリズムが知られています。^[8] チャンのアルゴリズムは2次元と3次元に使用され、クイックハルは高次元の凸包の計算に使用されます。^[9]

有限の点集合に対して、凸包は3次元の凸多面体、または一般には任意の次元数の凸多面体であり、その頂点は入力集合内の点の一部である。しかし、その表現は平面の場合ほど単純ではない。高次元では、凸多面体の頂点がわかっていても、その面の構築は簡単な作業ではなく、面が与えられた場合に頂点を構築するという二重の問題も同様である。出力される面情報のサイズは、入力頂点のサイズよりも指数的に大きくなる可能性があり、入力と出力が同程度のサイズの場合でも、高次元凸包の既知のアルゴリズムは、退化した入力の問題と、複雑性の高い中間結果の両方のために、出力に敏感ではない。^[10]

• 直交凸包

• Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein。アルゴリズム入門、第 2 版。MIT Press および McGraw-Hill、2001 年。ISBN 0-262-03293-7。セクション 33.3: 凸包の検出、pp. 947–957 。 
• Franco P. Preparata、SJ Hong。2次元および3次元の点の有限集合の凸包、Commun. ACM、vol. 20、no. 2、pp. 87–93、1977年。
• マーク・デ・バーグ;マーク・ヴァン・クレベルド;マーク・オーヴァーマースとオトフリード・シュワルツコップ(2000)。計算幾何学(改訂第 2 版)。スプリンガー・フェルラーグ。ISBN 978-3-540-65620-3。セクション 1.1: 例: 凸包 (2 次元凸包の従来のアルゴリズムについて説明します)。第 11 章: 凸包: 235 ～ 250 ページ (Clarkson と Shor による 3 次元凸包のランダム化アルゴリズムについて説明します)。

Wikibookのアルゴリズム実装には、凸包に関するページがあります。

• Weisstein、Eric W.「凸包」。MathWorld。
• 計算幾何学アルゴリズムライブラリCGALの 2D、3D、および dD 凸包
• 凸包、ドロネー三角形分割、ボロノイ図、半空間交差の Qhull コード
• Flash swf、Jarvis、Graham、Quick（分割統治法）、Chan アルゴリズムのデモ
• C# でのギフトラッピングアルゴリズム