|
数学における凸包（とつほう、）または凸包絡（とつほうらく、）は、与えられた集合を含む最小の凸集合である。例えば ''X'' がユークリッド平面内の有界な点集合のとき、その凸包は直観的には ''X'' をゴム膜で包んだときにゴム膜が作る図形として視認することができる〔, p. 3.〕。 精確に言えば、''X'' の凸包は ''X'' を含む全ての凸集合の交わり、あるいは同じことだが ''X'' に属する点の凸結合全体の成す集合として定義される。後者の定式化であれば、凸包をユークリッド空間だけでなく任意の実線型空間や、より一般に有向マトロイドに対して考えることができる。 平面上あるいは低次元ユークリッド空間内の有限点集合に対してその凸包を計算するアルゴリズム問題は、計算幾何学の基本的問題の一つである。 == 定理 == 与えられた点集合が凸集合であるとは、その集合に属する点の任意の対を結ぶ線分がその集合に含まれることを言うのであった。与えられた集合 ''X'' に対して、その凸包は以下の同値な条件： # ''X'' を含む（唯一の）最小の凸集合、 # ''X'' を含む凸集合全ての交わり、 # ''X'' に属する点から得られる凸結合全体の成す集合、 # ''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'' を含む: * 凸包作用素は「単調性」を持つ。即ち、二つの集合 ''X'', ''Y'' が ''X'' ⊆ ''Y'' を満たすならば、''X'' の凸包は ''Y'' の凸包に含まれる: * 凸包作用素は「冪等性」を持つ。即ち、任意の ''X'' に対して ''X'' の凸包の凸包は ''X'' の凸包に等しい: を満たす。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「凸包」の詳細全文を読む スポンサード リンク
|