凸包アルゴリズム （とつほうアルゴリズム）は、凸包 を求めるアルゴリズム である。数学 やコンピューターサイエンス で幅広い用途 がある。
計算幾何学 では、さまざまな計算複雑性 を持つ、有限の点のセットの凸包を計算するためのアルゴリズムが考案されている。
凸包アルゴリズムの計算量は、通常は入力の点の数である n に依存し 、また凸包上の点の数である h に依存する こともある。
アルゴリズムへの入力が直交座標系 上の有限個の順序なしの点の集合 である場合の一般的なケースを考える。
すべての点が同一線上ある場合以外では、それらの凸包は凸多角形 であり、それらの頂点は入力セット内の点である。その最も一般的な表現は、時計回りまたは反時計回りに境界に沿って並べられた頂点のリストである。一部のアプリケーションでは、凸多角形を一連の半平面 （英語版 ）
平面内の有限の点の集合の場合、凸多角形として表される凸包を見つける計算複雑性 は、還元 を使ってソート 以上であることが簡単に示せる。数値の集合
x
1
,
… … -->
,
x
n
{\displaystyle x_{1},\dots ,x_{n}}
(
x
1
,
x
1
2
)
,
… … -->
,
(
x
n
,
x
n
2
)
{\displaystyle (x_{1},x_{1}^{2}),\dots ,(x_{n},x_{n}^{2})}
凸曲線 である放物線 上にあるため、凸包の頂点が境界に沿って移動すると、番号のソートされた順序が生成されることが簡単にわかる。
x
1
,
… … -->
,
x
n
{\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年にカークパトリックとサイデルによって発見された（彼らはそれを「究極の凸包アルゴリズム （英語版 ） チャンのアルゴリズム （英語版 ）
グラハムスキャンで二次元の凸包を見つける過程。 既知の凸包アルゴリズムを公開順に並べている。各アルゴリズムの時間計算量は、入力点の数 n と凸包上の点の数 h で表される。最悪の場合では、 h は n と同じ大きさになる可能性がある。
ギフト包装法 ジャービス行進 — O （nh ）O （nh ）の時間計算量 がかかる。最悪の場合は Θ （n 2 ）かかる。グラハムスキャン （英語版 ） O （n log n ）ロナルド・グラハム によって公開された、もう少し洗練された、はるかに効率的なアルゴリズム。座標の1つまたは固定ベクトルに対する角度で、点がソート済みの場合、アルゴリズムには O（n ）時間がかかる。クイックハル （英語版 ） クイックソート アルゴリズムと同様に、期待時間計算量は O （n log n ）で、最悪の場合、 O （n 2 ）かかる可能性がある。分割統治法 — O （n log n ）n log n ）アルゴリズム。1977年にプレパラータとホンによって公開されました。このアルゴリズムは、3次元の場合にも適用できます。モノトーンチェーン アンドリューのアルゴリズム — O （n log n ）O （n ）の時間で実行できる。インクリメンタル凸包アルゴリズム — O （n log n ）カークパトリック-サイデルアルゴリズム （英語版 ） O （n log h ）低次元線形計画法 （英語版 ） チャンのアルゴリズム （英語版 ） O （n log h ）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 2 n ）で処理できる[ 1]
単純多角形（青）に対する凸包。4つのポケット（黄色）を持つ。青と黄色の両方を合わせた領域が凸包である。 単純多角形（自己交差を持たない多角形）の凸包は、その多角形によって複数の多角形に分割されている。そのうちの1つは多角形自体であり、残りは多角形境界の断片と凸包の一辺で囲まれたポケット である。単純多角形の凸包を構築する問題について多くのアルゴリズムが公開されていたが、それらのほぼ半分は正しくなかった[ 3] [ 4] グラハム & ヤオ (1983) 、あるいはリー (1983) による簡略版では、単一のスタックデータ構造 のみを使用する。彼らのアルゴリズムは、多角形の左端の頂点から時計回りにたどる。その際、まだポケットの中に位置すると判明してない頂点を格納していき、スタック上に凸多角形状の点のリストを作る。この各ステップでは、スタックのトップの点から、それと隣接するポケットではない頂点まで、多角形にそった経路をたどる。そしてこの新しい頂点とスタックの上から2つの頂点が凸状の形にならない場合、スタックのポップをしてから、最後に新しい頂点を追加する。時計回りの処理が開始点に達すると、このスタック内の頂点列が凸包となる[ 5] [ 6]
3次元の場合や、任意の次元の場合でも、多くのアルゴリズムが知られている[ 7] [ 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 , MR 729228 ^ 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 , MR 724699 ^ 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 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 Springer-Verlag . ISBN 978-3-540-65620-3 . https://archive.org/details/computationalgeo00berg
Weisstein, Eric W. "Convex Hull" . mathworld.wolfram.com (英語). 2D, 3D, and dD Convex Hull in CGAL , the Computational Geometry Algorithms LibraryQhull code for Convex Hull, Delaunay Triangulation, Voronoi Diagram, and Halfspace Intersection Demo as Flash swf , Jarvis, Graham, Quick (divide and conquer) and Chan algorithmsGift wrapping algorithm in C# 
