凸包
凸包
(convex hull から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/17 04:35 UTC 版)
ナビゲーションに移動 検索に移動
数学における凸包（とつほう、英: convex hull）または凸包絡（とつほうらく、英: convex envelope）は、与えられた集合を含む最小の凸集合である。例えば X がユークリッド平面内の有界な点集合のとき、その凸包は直観的には X をゴム膜で包んだときにゴム膜が作る図形として視認することができる[1]。
精確に言えば、X の凸包は X を含む全ての凸集合の交わり、あるいは同じことだが X に属する点の凸結合全体の成す集合として定義される。後者の定式化であれば、凸包をユークリッド空間だけでなく任意の実線型空間や、より一般に有向マトロイドに対して考えることができる[2]。
平面上あるいは低次元ユークリッド空間内の有限点集合に対してその凸包を計算するアルゴリズム問題は、計算幾何学の基本的問題の一つである。
定理
与えられた点集合が凸集合であるとは、その集合に属する点の任意の対を結ぶ線分がその集合に含まれることを言うのであった。与えられた集合 X に対して、その凸包は以下の同値な条件：
の何れか一つ（従って全て）を満たす集合として定義される。
一つ目の定式化については、任意の X に対して実際に X を含む最小の凸集合が存在して一つに定まることはそのままでは明らかなことでない。しかし二つ目の定式化では、X を含む全ての凸集合の交わりは明確に定まり（特に全体集合は凸であるから、これは空積にはならない）、かつこの交わりは（交わりの定義によって）X を含む任意の凸集合 Y に含まれるから、この交わりが X を含む唯一最小なる凸集合に他ならないことがわかる。
また、X を含む各凸集合は（それが凸であるという仮定によって）X に属する点の凸結合をすべて含むから、従ってこのような凸結合全体の成す集合は X を含む凸集合全ての交わりに含まれる。逆に、そのような凸結合全体の成す集合はそれ自身 X を含む凸集合ゆえ X を含む凸集合全ての交わりを含むから、これら二つの定式化が同じ集合を与えていることが知れる。
実は、凸包に関するカラテオドリの定理によれば、X が N-次元線型空間の部分集合であるとき、凸包を求めるには上記定義において高々 N + 1 個の点の凸結合を考えれば十分である。従って特に、平面上の三点以上を含む集合の凸包は X に属する点の任意の三つ組から得られる三角形全てに亙る合併に一致し、同様により一般の N-次元空間における凸包は X に属する高々 N + 1 点を頂点として定まる単体全てに亙る合併に一致する。
X の凸包が閉集合となるとき（よくあるのが例えば X が有限集合やもっと一般にコンパクト集合のとき）、それは X を含む閉半空間全ての交わりと一致する。このとき、超平面分離定理は、凸包に属さない各点が半空間によって凸包と分離されることを保証する。しかし、このようなやり方で表すことのできない凸集合および凸包が存在する。例えばその一つは、その境界に一点しか含まない開半平面によって与えられる。
より抽象的に言えば、凸包をとる作用素 Conv() は閉包作用素を特徴づける三性質：
- 凸包作用素は「拡大性質」を持つ。即ち、任意の集合 X に対してその凸包は X を含む:
有限な点集合の凸包は、それに属する点から得られる凸結合全体の成す集合である。凸結合における S の各点 xi に掛かる重みあるいは係数 αi は、全て正かつそれらの総和が 1 となるものであり、これらの重みは点の間の重み付き平均の計算に用いられる。このような係数の組を選ぶごとに凸包に属する点が一つ定まり、係数として可能な全ての組を考えることによって凸包の全体が得られる。式にすれば、凸包は
S の点が全て一つの直線上に載っているならば、S の凸包はもっとも外側にある二点を結ぶ線分になる。また、集合 S が平面上の（つまり二次元の）空でない有限部分集合のとき、S 全体をゴムバンドでぐるりと囲んでから、これを放して縮まる状況を想像すると、ゴムバンドがピンと張った状況で S の凸包を見取ることができる[1]。
二次元において、凸包は最左点と最右点の間を引き延ばしてできる「上包」(upper hull) と「下包」(lower hull) と呼ばれる二つの多角形の鎖に分けることがある。より一般に言えば、任意次元で一般の位置にある点の集合に対して、凸包の各刻面は（凸包とその直上の点を分離することで）上方または下方に向き付けられる。上方を向く刻面全ての合併が上包と呼ばれる位相的円板を成すのである。同様に下包は下方向き刻面全体の合併を言う[3]
凸包の計算
計算幾何学において、点やその他の幾何学的対象のなす有限集合の凸包を計算するアルゴリズムが数多く知られている。ギフト包装法などがある。
「凸包の計算」というのは、曖昧さ無く効果的に求める凸図形を表すデータを構築することを意味する。凸包アルゴリズムの計算量は通例、入力点の数 n と凸包に属する点（出力点）の数 h とに関して評価される。
二次元及び三次元の点集合に対して、計算量 O(n log h) で凸包を計算できる出力依存アルゴリズムが知られている。三次元より高次の d-次元では、凸包の計算時間は最悪の場合で 
