凸包アルゴリズム

凸包アルゴリズム（とつほうアルゴリズム）は、凸包を求めるアルゴリズムである。数学やコンピューターサイエンスで幅広い用途がある。

計算幾何学では、さまざまな計算複雑性を持つ、有限の点のセットの凸包を計算するためのアルゴリズムが考案されている。

凸包アルゴリズムの計算量は、通常は入力の点の数である n に依存し、また凸包上の点の数である h に依存することもある。

平面の場合

アルゴリズムへの入力が直交座標系上の有限個の順序なしの点の集合である場合の一般的なケースを考える。

すべての点が同一線上ある場合以外では、それらの凸包は凸多角形であり、それらの頂点は入力セット内の点である。その最も一般的な表現は、時計回りまたは反時計回りに境界に沿って並べられた頂点のリストである。一部のアプリケーションでは、凸多角形を一連の半平面（英語版）の交点として表すことが向いている。

計算量の下限

平面内の有限の点の集合の場合、凸多角形として表される凸包を見つける計算複雑性は、還元を使ってソート以上であることが簡単に示せる。数値の集合 $x_{1},\dots ,x_{n}$ について、 $(x_{1},x_{1}^{2}),\dots ,(x_{n},x_{n}^{2})$ で表される平面上の点の集合を考える。それらは凸曲線である放物線上にあるため、凸包の頂点が境界に沿って移動すると、番号のソートされた順序が生成されることが簡単にわかる。 $x_{1},\dots ,x_{n}$ 。明らかに、記述された数値のポイントへの変換と、それらのソートされた順序の抽出には線形時間が必要である。したがって、一般的なケースでは、凸包はソートよりも速く計算できない。

ソートで標準とされる Ω（n log n）の下限は、決定木モデル内で証明されています。決定木モデルは数値比較のみを実行でき、算術演算は実行できないもので、凸包は算出できない。凸包に適したモデルである代数決定木（英語版）モデルでも、ソートには Ω（n log n）時間が必要であり、このモデルでは凸包にも Ω（n log n）時間が必要である^[1]。ただし、たとえば整数のソート（英語版）アルゴリズムを使用して、数値を O（n log n）時間よりも速く並べ替えることができるコンピューター演算のモデルでは、平面凸包もより速く計算できる。例えば、凸包のグラハムスキャン（英語版）アルゴリズムは1回のソートと線形時間の処理で実現される。

最良の出力依存アルゴリズム

上記のように、入力サイズ n の凸包を見つける計算量は、Ω（n log n）を下限とする。ただし、一部の凸包アルゴリズムの計算量は、入力サイズ nと出力サイズ h （凸包上の点の数）の両方で決まる。このようなアルゴリズムは、出力依存アルゴリズム（英語版）と呼ばれる。h = o（n）の場合、これらは、Θ（n log n）アルゴリズムよりも漸近的に効率的と考えられる。

出力依存の凸包アルゴリズムの最悪時間計算量の下限は、平面の場合で Ω（n log h）であることが確立された。^[1]この最良の時間計算量を達成するアルゴリズムは複数ある。最初のものは、1986年にカークパトリックとサイデルによって発見された（彼らはそれを「究極の凸包アルゴリズム（英語版）」と呼んだ）。1996年には、さらに単純なアルゴリズム、チャンのアルゴリズム（英語版）がチャンによって開発された。

アルゴリズム

グラハムスキャンで二次元の凸包を見つける過程。

既知の凸包アルゴリズムを公開順に並べている。各アルゴリズムの時間計算量は、入力点の数 n と凸包上の点の数 h で表される。最悪の場合では、 h は n と同じ大きさになる可能性がある。

ギフト包装法、別名: ジャービス行進 — O（nh）
最も単純な（しかし最悪の場合の時間効率が良くない）平面アルゴリズムの1つ。1970年にチャンドとカプール、1973年にジャービスによって別々に発見された。O（nh）の時間計算量がかかる。最悪の場合は Θ（n ²）かかる。
グラハムスキャン（英語版） — O（n log n）
1972年にロナルド・グラハムによって公開された、もう少し洗練された、はるかに効率的なアルゴリズム。座標の1つまたは固定ベクトルに対する角度で、点がソート済みの場合、アルゴリズムには O（n）時間がかかる。
クイックハル（英語版）
1977年にW.エディによって、1978年にA.Bykatによって別々に発見された。クイックソートアルゴリズムと同様に、期待時間計算量は O（n log n）で、最悪の場合、 O（n ²）かかる可能性がある。
分割統治法 — O（n log n）
こちらも、O（n log n）アルゴリズム。1977年にプレパラータとホンによって公開されました。このアルゴリズムは、3次元の場合にも適用できます。
モノトーンチェーン、別名: アンドリューのアルゴリズム — O（n log n）
1979年にA.M.アンドリューによって発表された。このアルゴリズムは、点を辞書式に座標で並べ替えるグラハムスキャンの変形と見なすことができる。入力がすでにソートされている場合、 O（n）の時間で実行できる。
インクリメンタル凸包アルゴリズム — O（n log n）
1984年にマイケル・カーライによって発表された。
カークパトリック-サイデルアルゴリズム（英語版） — O（n log h）
最初の最適な出力依存ｎアルゴリズム。分割統治アルゴリズムに、征服前の結婚（marriage-before-conquest）と低次元線形計画法（英語版）による変更を加えたもの。1986年にカークパトリックとサイデルによって発表された。
チャンのアルゴリズム（英語版） — O（n log h）
1996年にチャンによって作成されたより単純で最適な出力依存のアルゴリズム。これは、ギフト包装法と小さな入力のサブセットに対する O（n log n）アルゴリズム（グラハムスキャンなど）の実行を組み合わせたもの。

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

このシンプルなヒューリスティックは、凸包アルゴリズムの実装の最初のステップとして、パフォーマンスを向上させるためによく使われる。これは、1978年のセリム・アクルと G.T.トゥーサンによる効率的な凸包アルゴリズムをベースとしている。とにかく凸包の一部ではない多くの点をすばやく除外するというアイデアである。この方法ではまず、x 座標が最低と最高の2つの点と、 y 座標が最低と最高の2つの点を見つける（これらの各操作は O（n）となる）。これらの4つの点は凸四角形を形成し、この4点以外のこの四角形内のすべての点は凸包の一部ではない。この四角形にあるこれらすべての点を見つけることも O（n）であり、したがって、操作全体は O（n）となる。必要に応じて、 x 座標と y 座標の合計が最小および最大の点、および x 座標と y 座標の差が最小および最大の点も追加して、不規則な凸八角形を形成して除外を行います。点が確率変数となる場合、つまり現実でよくあるケースで、この除外処理によって、凸包アルゴリズムが線形時間で完了することが期待される^[2]。

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

これまでの説明では、すべての入力ポイントが事前にわかっている場合を想定していたが、他の2つのシチュエーションを想定することもできる^[1]。

オンライン凸包問題：入力点は1つずつ順番に渡される。各点が入力に到着するたび、これまでに取得した点の集合の凸包を効率的に計算する。
動的凸包（英語版）のメンテナンス：入力点を順番に追加または削除できる。凸包を、追加/削除操作のたびに更新する必要がある。

点を追加すると、凸包の頂点の数が最大で1増える可能性があり、削除すると、 n 頂点の凸包が n - 1 頂点に変換される可能性がある。

オンライン凸包問題は、点ごとにO（log n）で処理できる。これは、漸近的に最適である。動的凸包は、操作ごとに O（log ² n）で処理できる^[1]。

単純多角形

単純多角形（青）に対する凸包。4つのポケット（黄色）を持つ。青と黄色の両方を合わせた領域が凸包である。

単純多角形（自己交差を持たない多角形）の凸包は、その多角形によって複数の多角形に分割されている。そのうちの1つは多角形自体であり、残りは多角形境界の断片と凸包の一辺で囲まれたポケットである。単純多角形の凸包を構築する問題について多くのアルゴリズムが公開されていたが、それらのほぼ半分は正しくなかった^[3]。マッカラムとエイビスは最初の正しいアルゴリズムを提供した^[4]。グラハム & ヤオ (1983)、あるいはリー (1983) による簡略版では、単一のスタックデータ構造のみを使用する。彼らのアルゴリズムは、多角形の左端の頂点から時計回りにたどる。その際、まだポケットの中に位置すると判明してない頂点を格納していき、スタック上に凸多角形状の点のリストを作る。この各ステップでは、スタックのトップの点から、それと隣接するポケットではない頂点まで、多角形にそった経路をたどる。そしてこの新しい頂点とスタックの上から2つの頂点が凸状の形にならない場合、スタックのポップをしてから、最後に新しい頂点を追加する。時計回りの処理が開始点に達すると、このスタック内の頂点列が凸包となる^[5]^[6]。

高次元

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

有限個の点の集合の場合、凸包は3次元では入力の点の集合の一部から成る凸多面体、任意の次元では凸ポリトープである。ただし、その表現は平面の場合ほど単純ではない。高次元では、凸ポリトープの頂点がわかっている場合でも面を作成するのは自明ではないし、面から頂点を作成するのも自明ではない。出力面の情報のサイズは、入力頂点のサイズよりも指数関数的に大きくなる可能性があり、入力と出力の両方が同等のサイズである場合でも、高次元の凸包の既知のアルゴリズムは、入力の縮退の問題と非常に複雑な中間結果に関する問題の両方の理由から出力依存ではない^[9]。

出典

^ ^a ^b ^c ^d Preparata, Shamos, Computational Geometry, Chapter "Convex Hulls: Basic Algorithms"
^ Luc Devroye and Godfried Toussaint, "A note on linear expected time algorithms for finding convex hulls," Computing, Vol. 26, 1981, pp. 361-366.
^ Aloupis. “A History of Linear-time Convex Hull Algorithms for Simple Polygons”. October 11, 2020閲覧。
^ McCallum, Duncan; Avis, David (1979), “A linear algorithm for finding the convex hull of a simple polygon”, Information Processing Letters 9 (5): 201–206, doi:10.1016/0020-0190(79)90069-3, MR 552534
^ Graham, Ronald L.; Yao, F. Frances (1983), “Finding the convex hull of a simple polygon”, Journal of Algorithms 4 (4): 324–331, doi:10.1016/0196-6774(83)90013-5, MR729228
^ Lee, D. T. (1983), “On finding the convex hull of a simple polygon”, International Journal of Computer and Information Sciences 12 (2): 87–98, doi:10.1007/BF00993195, MR724699
^ See David Mount's Lecture Notes, including Lecture 4 for recent developments, including Chan's algorithm.
^ Barber, C. Bradford; Dobkin, David P.; Huhdanpaa, Hannu (1 December 1996). “The quickhull algorithm for convex hulls”. ACM Transactions on Mathematical Software 22 (4): 469–483. doi:10.1145/235815.235821.
^ Avis, David; Bremner, David; Seidel, Raimund (1997), “How good are convex hull algorithms?”, Computational Geometry: Theory and Applications 7 (5–6): 265–301, doi:10.1016/S0925-7721(96)00023-5 .

参考文献

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#

[ps-1] Preparata, Shamos, Computational Geometry, Chapter "Convex Hulls: Basic Algorithms"

[2] Luc Devroye and Godfried Toussaint, "A note on linear expected time algorithms for finding convex hulls," Computing, Vol. 26, 1981, pp. 361-366.

[3] Aloupis. “A History of Linear-time Convex Hull Algorithms for Simple Polygons”. October 11, 2020閲覧。

[4] McCallum, Duncan; Avis, David (1979), “A linear algorithm for finding the convex hull of a simple polygon”, Information Processing Letters 9 (5): 201–206, doi:10.1016/0020-0190(79)90069-3, MR 552534

[5] Graham, Ronald L.; Yao, F. Frances (1983), “Finding the convex hull of a simple polygon”, Journal of Algorithms 4 (4): 324–331, doi:10.1016/0196-6774(83)90013-5, MR729228

[6] Lee, D. T. (1983), “On finding the convex hull of a simple polygon”, International Journal of Computer and Information Sciences 12 (2): 87–98, doi:10.1007/BF00993195, MR724699

[7] See David Mount's Lecture Notes, including Lecture 4 for recent developments, including Chan's algorithm.

[8] Barber, C. Bradford; Dobkin, David P.; Huhdanpaa, Hannu (1 December 1996). “The quickhull algorithm for convex hulls”. ACM Transactions on Mathematical Software 22 (4): 469–483. doi:10.1145/235815.235821.

[9] Avis, David; Bremner, David; Seidel, Raimund (1997), “How good are convex hull algorithms?”, Computational Geometry: Theory and Applications 7 (5–6): 265–301, doi:10.1016/S0925-7721(96)00023-5 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]