凸包アルゴリズム
凸包アルゴリズム(とつほうアルゴリズム)は、凸包を求めるアルゴリズムである。数学やコンピューターサイエンスで幅広い用途がある。
計算幾何学では、さまざまな計算複雑性を持つ、有限の点のセットの凸包を計算するためのアルゴリズムが考案されている。
凸包アルゴリズムの計算量は、通常は入力の点の数である n に依存し、また凸包上の点の数である h に依存することもある。
このアルゴリズムは、3次元の場合にも適用できます。
モノトーンチェーン、別名: アンドリューのアルゴリズム — O(n log n)1979年にA.M.アンドリューによって発表された。このアルゴリズムは、点を辞書式に座標で並べ替えるグラハムスキャンの変形と見なすことができる。入力がすでにソートされている場合、 O(n)の時間で実行できる。
インクリメンタル凸包アルゴリズム — O(n log n)1984年にマイケル・カーライによって発表された。
カークパトリック-サイデルアルゴリズム(英語版) — O(n log h)最初の最適な出力依存nアルゴリズム。分割統治アルゴリズムに、征服前の結婚(marriage-before-conquest)と低次元線形計画法(英語版)による変更を加えたもの。1986年にカークパトリックとサイデルによって発表された。
チャンのアルゴリズム(英語版) — O(n log h)1996年にチャンによって作成されたより単純で最適な出力依存のアルゴリズム。これは、ギフト包装法と小さな入力のサブセットに対する O(n log n)アルゴリズム(グラハムスキャンなど)の実行を組み合わせたもの。
平面内の有限の点の集合の場合、凸多角形として表される凸包を見つける計算複雑性は、還元を使ってソート以上であることが簡単に示せる。数値の集合 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}} 。