凸包アルゴリズム

凸包アルゴリズム

凸包アルゴリズムは、与えられた点の集合を包含する最小の凸多角形（または凸多面体）を求めるアルゴリズムです。数学やコンピュータサイエンスの様々な分野で応用されており、計算幾何学における基本的な問題の一つです。

平面における凸包

平面上の点の集合が与えられた場合、その凸包は凸多角形になります。この凸多角形の頂点は入力点集合に含まれます。凸包を表現する方法として、頂点を時計回りまたは反時計回りの順にリスト化したり、半平面の交点として表現する方法があります。

計算量の下限

平面上の点の集合に対する凸包問題を解く計算量の理論的な下限は、ソート問題と同程度であることが知られています。具体的には、数値の集合をソートする問題は、その数値の組から作成される平面上の点の集合に対する凸包問題に帰着できます。ソートアルゴリズムの計算量の下限は Ω(n log n) であるため、凸包問題も同様の計算量が必要となります。

決定木モデルにおいて数値の比較のみを行う場合、ソートには Ω(n log n) の計算量が必要となります。同様に、代数決定木モデルにおいても、凸包問題を解くには Ω(n log n) の計算量が必要となります。

ただし、整数のソートアルゴリズムなどを用いることで、ソートを O(n log n) より高速に行えるモデルでは、凸包問題もより高速に解くことが可能になります。例えば、グラハムスキャンアルゴリズムは、ソートと線形時間処理を組み合わせることで凸包を計算します。

出力依存アルゴリズム

凸包アルゴリズムの計算量は、入力点の数 n に依存するだけでなく、凸包上の点の数 h にも依存します。h が n に比べて小さい場合、出力依存アルゴリズムを用いることで、効率的に凸包を計算できます。

平面の場合、出力依存アルゴリズムの最悪時間計算量の下限は Ω(n log h) です。この計算量を達成するアルゴリズムとして、カークパトリック-サイデルアルゴリズムやチャンのアルゴリズムがあります。

代表的なアルゴリズム

ギフト包装法 (ジャービス行進法)

最も単純なアルゴリズムの一つで、時間計算量は O(nh) です。点の集合から凸包の頂点を一つずつ探し出し、凸包を構築します。最悪の場合には O(n^2) の計算量を要します。

グラハムスキャン

より効率的なアルゴリズムで、時間計算量は O(n log n) です。座標または固定ベクトルに対する角度で点をソートすることで、凸包を効率的に計算します。点がソート済みの場合、アルゴリズムの計算時間は O(n) になります。

クイックハル

クイックソートと同様の考え方を用いたアルゴリズムで、期待時間計算量は O(n log n) です。最悪の場合には O(n^2) の計算量になります。

分割統治法

点を分割し、再帰的に凸包を求め、それらを結合することで凸包を計算します。時間計算量は O(n log n) です。3次元の場合にも適用できます。

モノトーンチェーン法 (アンドリューのアルゴリズム)

点を辞書式にソートするグラハムスキャンの変形版で、時間計算量は O(n log n) です。入力がソート済みの場合は O(n) で実行できます。

インクリメンタル凸包アルゴリズム

点を一つずつ追加しながら凸包を更新するアルゴリズムで、時間計算量は O(n log n) です。

カークパトリック-サイデルアルゴリズム

最初の最適な出力依存アルゴリズムで、時間計算量は O(n log h) です。分割統治法に、征服前の結婚と低次元線形計画法を組み合わせたものです。

チャンのアルゴリズム

より単純な出力依存アルゴリズムで、時間計算量は O(n log h) です。ギフト包装法と O(n log n) アルゴリズムを組み合わせたものです。

アクル-トゥーサンヒューリスティック

凸包の頂点ではない点を効率的に削除するためのヒューリスティックです。x座標とy座標の最大値、最小値を持つ点を利用して凸四角形を形成し、その内側の点を削除します。この処理は O(n) で完了します。点を確率変数として扱う場合、この除外処理によって凸包アルゴリズムが線形時間で完了することが期待できます。

オンライン/動的凸包問題

オンライン凸包問題

入力点が逐次的に与えられる場合、各点が入力された時点で凸包を効率的に計算する必要があります。この問題は点ごとに O(log n) で処理でき、漸近的に最適です。

動的凸包問題

点の追加と削除が可能な場合、操作ごとに凸包を更新する必要があります。この問題は、操作ごとに O(log^2 n) で処理できます。

単純多角形

単純多角形（自己交差を持たない多角形）の凸包は、多角形を複数の領域に分割します。そのうち一つは多角形自体であり、残りは多角形の境界の一部と凸包の一辺で囲まれたポケットです。単純多角形の凸包を求めるアルゴリズムとして、マッカラムとエイビスによるアルゴリズムや、グラハムとヤオ、あるいはリーによる簡略版があります。これらのアルゴリズムでは、単一のスタックデータ構造を用いて、多角形の左端から時計回りに辿り、スタックに凸多角形の頂点を追加していきます。

高次元の凸包

3次元以上の場合でも、凸包を計算するアルゴリズムは存在します。例えば、チャンのアルゴリズムは2次元と3次元に、クイックハルは高次元の凸包計算に利用できます。ただし、高次元では凸包の表現が複雑になり、出力サイズが入力サイズよりも指数関数的に大きくなることがあります。そのため、高次元の凸包アルゴリズムは、入力の縮退や中間結果の複雑さといった問題から、出力依存型ではないものが多くなります。

関連項目

直交凸包

参考文献

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 33.3: Finding the convex hull, pp. 947–957.
Franco P. Preparata, S.J. Hong. Convex Hulls of Finite Sets of Points in Two and Three Dimensions, Commun. ACM, vol. 20, no. 2, pp. 87–93, 1977.
Mark de Berg; Marc van Kreveld; Mark Overmars & Otfried Schwarzkopf (2000). Computational Geometry (2nd revised ed.). Springer-Verlag. ISBN 978-3-540-65620-3. Section 1.1: An Example: Convex Hulls (describes classical algorithms for 2-dimensional convex hulls). Chapter 11: Convex Hulls: pp. 235–250 (describes a randomized algorithm for 3-dimensional convex hulls due to Clarkson and Shor).

外部リンク

Weisstein, Eric W. "Convex Hull". mathworld.wolfram.com (英語).
2D, 3D, and dD Convex Hull in CGAL, the Computational Geometry Algorithms Library
Qhull code for Convex Hull, Delaunay Triangulation, Voronoi Diagram, and Halfspace Intersection
Demo as Flash swf, Jarvis, Graham, Quick (divide and conquer) and Chan algorithms
* Gift wrapping algorithm in C#

もう一度検索