凸包アルゴリズム

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

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

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

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

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

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

ソートで標準とされる Ω（n log n）の下限は、決定木モデル内で証明されています。決定木モデルは数値比較のみを実行でき、算術演算は実行できないもので、凸包は算出できない。凸包に適したモデルであるモデルでも、ソートには Ω（n log n）時間が必要であり、このモデルでは凸包にも Ω（n log n）時間が必要であるPreparata, Shamos, Computational Geometry, Chapter "Convex Hulls: Basic Algorithms"。ただし、たとえばアルゴリズムを使用して、数値を O（n log n）時間よりも速く並べ替えることができるコンピューター演算のモデルでは、平面凸包もより速く計算できる。例えば、凸包のアルゴリズムは1回のソートと線形時間の処理で実現される。

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

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

アルゴリズム

既知の凸包アルゴリズムを公開順に並べている。各アルゴリズムの時間計算量は、入力点の数 n と凸包上の点の数 h で表される。最悪の場合では、 h は n と同じ大きさになる可能性がある。ギフト包装法、別名: ジャービス行進 — O（nh）最も単純な（しかし最悪の場合の時間効率が良くない）平面アルゴリズムの1つ。1970年にチャンドとカプール、1973年にジャービスによって別々に発見された。O（nh）の時間計算量がかかる。最悪の場合は Θ（n 2）かかる。 — O（n log n）1972年にロナルド・グラハムによって公開された、もう少し洗練された、はるかに効率的なアルゴリズム。座標の1つまたは固定ベクトルに対する角度で、点がソート済みの場合、アルゴリズムには O（n）時間がかかる。 1977年にW.エディによって、1978年にA.Bykatによって別々に発見された。クイックソートアルゴリズムと同様に、期待時間計算量は O（n log n）で、最悪の場合、 O（n 2）かかる可能性がある。分割統治法 — 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 座標の差が最小および最大の点も追加して、不規則な凸八角形を形成して除外を行います。点が確率変数となる場合、つまり現実でよくあるケースで、この除外処理によって、凸包アルゴリズムが線形時間で完了することが期待されるLuc Devroye and Godfried Toussaint, "A note on linear expected time algorithms for finding convex hulls," Computing, Vol. 26, 1981, pp. 361-366.。

オンライン／動的凸包問題これまでの説明では、すべての入力ポイントが事前にわかっている場合を想定していたが、他の2つのシチュエーションを想定することもできるPreparata, Shamos, Computational Geometry, Chapter "Convex Hulls: Basic Algorithms"。

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

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

オンライン凸包問題は、点ごとにO（log n）で処理できる。これは、漸近的に最適である。動的凸包は、操作ごとに O（log 2 n）で処理できるPreparata, Shamos, Computational Geometry, Chapter "Convex Hulls: Basic Algorithms"。

単純多角形

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

高次元 3次元の場合や、任意の次元の場合でも、多くのアルゴリズムが知られているSee David Mount's Lecture Notes, including Lecture 4 for recent developments, including Chan's algorithm.。チャンのアルゴリズムは2次元と3次元に、クイックハルは高次元の凸包の計算に使用できる。

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

凸包アルゴリズム

Źródło i licencja