アルゴリズムへの入力がデカルト平面上の点の有限の非順序集合である場合の一般的なケースを考えてみよう。 重要な特殊ケースとして、点が単純な多角形の境界を横断する順序で与えられる場合については、別のサブセクションで後述する。
すべての点が同じ線上にない場合、その凸包は入力セットの点のいくつかを頂点とする凸多角形となる。 その最も一般的な表現は、境界線に沿って時計回りまたは反時計回りに並べた頂点のリストです。
計算量の下界編集
平面上の有限の点集合に対して、凸多角形として表現された凸包を求める計算量の下界は、以下の削減を用いてソートの場合と同じであることが簡単に示される。 集合x 1 , … , x n に対して {displaystyle x_{1},\dots ,x_{n}}} とする。
sortする数 点 ( x 1 , x 1 2 ) , … , ( x n , x n 2 ) {displaystyle (x_{1},x_{1}^{2}),\dots ,(x_{n},x_{n}^{2})} の集合を考える。
平面上の点のうち、1点。 これらは凸曲線である放物線上にあるので、凸包の頂点を境界に沿って横切ると、数x 1 , … , x n {displaystyle x_{1},\dots ,x_{n}} の並び順になることは容易に理解できる。
. 明らかに、記述された数値の点への変換とその並べ替え順序の抽出に線形時間が必要である。 したがって、一般にn個の点の凸包をソートより速く計算することはできない。
ソートの標準的なΩ(n log n)下限は、数値比較のみで算術演算ができない決定木モデルで証明されているが、このモデルでは凸包は全く計算されない。 また、ソートは凸包に適した計算の代数的決定木モデルでもΩ(n log n)の時間を必要とし、このモデルでは凸包もΩ(n log n)の時間を必要とする。 しかし、整数のソートアルゴリズムを用いるなどして、O(n log n)時間よりも速く数をソートできるコンピュータ演算のモデルでは、平面凸包もより速く計算できる。凸包のグラハム・スキャン・アルゴリズムは、単一のソートステップと、その後の線形量の追加作業から構成される。
Optimal Output-sensitive algorithmsEdit
上述のように、入力サイズnの関数として凸包を求める複雑さはΩ(n log n)で下界となる。 しかし、いくつかの凸包アルゴリズムの複雑さは、入力サイズnと出力サイズh（包内の点数）の両方で特徴付けることができる。 このようなアルゴリズムは、出力に依存するアルゴリズムと呼ばれる。 h=o(n)の場合、漸近的にΘ(n log n)アルゴリズムより効率的である。
出力に敏感な凸包アルゴリズムの最悪の場合の実行時間の下界は、平面の場合、Ω（n log h）であることが確立された。 この最適な時間複雑性を達成するアルゴリズムは幾つかある。 最も古いものは、1986年にKirkpatrickとSeidelによって紹介されたものである（彼はこれを「究極の凸包アルゴリズム」と呼んだ）。
AlgorithmsEdit
以下は既知の凸包アルゴリズムであり、初版の順に並んでいる。 各アルゴリズムの時間計算量は、入力点の数nと外皮上の点の数hで示されている。最悪の場合、hはnと同じくらいになることに注意。
- Gift wrapping, a.k.a. Jarvis march – O(nh)
最も単純（最悪の場合最も時間効率が良くないが）な平面アルゴリズムの一つ。 1970年にChand & Kapur、1973年にR. A. Jarvisが独自に考案した。 時間計算量はO(nh)で、nは集合の点の数、hは外皮の点の数である。 - Graham scan – O(n log n)
Ronald Grahamが1972年に発表した、やや洗練された、しかしはるかに効率的なアルゴリズムである。 もし点が既に座標の一つか固定ベクトルに対する角度でソートされているなら、このアルゴリズムはO(n)時間を要する。 - Quickhull
1977年にW. Eddyが、1978年にA. Bykatが独自に作成した。 クイックソート・アルゴリズムと同様に、期待される時間複雑度はO(n log n)であるが、最悪の場合O(n2)に退化する可能性がある。 - Divide and conquer – O(n log n)
1977年にプレパラタとホンが発表したもう一つのO(n log n)のアルゴリズムである。 このアルゴリズムは3次元の場合にも適用できる。 - Monotone chain, a.k.a. Andrew’s algorithm- O(n log n)
A. M. Andrewによって1979年に発表されたものである。 このアルゴリズムは、点の座標を辞書式にソートするグラハムスキャンの変種と見ることができる。 - Incremental convex hull algorithm – O(n log n)
1984年にマイケル・カレーにより発表された。 征服前の結婚と低次元線形計画法を用いて、分割統治法を修正したものである。 1986年にKirkpatrick and Seidelによって発表された。 - Chan’s algorithm – O(n log h)
1996年にChanによって作られた、より簡単な最適出力考慮アルゴリズム。
Akl-Toussaint heuristicEdit
以下の単純なヒューリスティックは、凸包アルゴリズムの実装において、そのパフォーマンスを向上させる最初のステップとしてよく使われるものである。 これは、Selim Akl と G. T. Toussaint, 1978 による効率的な凸包アルゴリズムに基づくものである。 このアイデアは，とにかく凸包の一部にならないような多くの点を素早く除外することである． この方法は、以下の考えに基づいている。 x座標の最小値と最大値を持つ2点、y座標の最小値と最大値を持つ2点を求める。 (これらの操作はそれぞれO(n)を要する)。 この4点は凸の四辺形を形成し、この四辺形に横たわる点（最初に選んだ4つの頂点を除く）は凸包に含まれないものである。 この四辺形の中にある点をすべて見つけるのもO(n)であり、したがって、この操作全体はO(n)である。 また、x座標とy座標の和が最小と最大の点、およびx座標とy座標の差が最小と最大の点も四角形に加えることができ、不規則凸八角形を形成するが、その内部は安全に捨てることができる。 点が確率変数である場合、確率密度関数の狭い、しかし一般的に遭遇するクラスに対して、この捨て去る前処理ステップは、凸包アルゴリズムの最悪の場合の複雑さがnの2次であっても、線形期待時間で凸包アルゴリズムを実行する。
- オンライン凸包問題： 入力点を1つずつ順次得る。 各点が入力に到着した後、これまでに得られた点集合に対する凸包を効率的に計算しなければならない。
- 動的凸包維持。
点の挿入は凸包の頂点を最大で1個増やすことができ、削除はn-頂点の凸包をn-1-頂点のものに変換することができる。
simple polygonEdit
単純多角形の凸包は多角形によって分割され、そのうちの1つは多角形自身、残りは多角形の境界の一部と1つの外皮辺で囲まれたポケットである。 単純多角形の凸包を構成する問題に対して多くのアルゴリズムが発表されているが、その半分近くは不正確である。McCallumとAvisは最初の正しいアルゴリズムを提供した。後のGraham & Yao (1983) and Lee (1983) による単純化では単一のスタックデータ構造のみを使用している。 彼らのアルゴリズムは、ポリゴンを時計回りに、その左端の頂点から順に走査する。 その際、ポケット内にあるとまだ特定されていない頂点の凸の列をスタックに格納する。 各ステップにおいて、アルゴリズムは、スタックトップから、スタックトップに隣接する2つのポケットのいずれにも属さない次の頂点まで、ポリゴンに沿った経路をたどります。 そして，この新しい頂点と一緒にスタックの上の2つの頂点が凸の位置にない間に，スタックをポップアップし，最後に新しい頂点をスタックに押し込む． 時計回りの走査が開始点に到達すると、アルゴリズムはスタックの頂点の列を船型として返す
。