凸包

数学における凸包（とつほう、英語: convex hull）は、ある集合に含まれる全ての点を含み、かつそれ自体が最も小さい凸集合となるものです。

例えば、平面上にある有限個の点の集まりを考えたとき、その凸包は、あたかも点集合をピンで囲み、その周囲にゴムバンドをかけたときにできる形のようにイメージできます。このゴムバンドがピンと張った状態で作る領域が凸包に相当します。

より厳密には、凸包はいくつかの同等な定義が可能です。一つは、与えられた集合を内部に含む全ての凸集合の共通部分として定義されます。また、集合に属する点の任意の凸結合（点を非負の係数で重み付けし、その係数の合計が1になる線形結合）全体の集合としても定義されます。この凸結合による定義は、ユークリッド空間だけでなく、より広い範囲の線型空間や幾何学的構造に対しても適用できます。

性質

凸包は、以下のようないくつかの重要な性質を持ちます。

拡大性: 元の集合は常にその凸包に含まれます。
単調性: ある集合が別の集合に含まれるならば、前者の凸包は後者の凸包に含まれます。
冪等性: 凸包の凸包は元の凸包と一致します。

これらの性質は、凸包を一種の「閉包作用素」と見なせることを示しています。

有限点集合の凸包

有限個の点からなる集合の場合、その凸包は、元の点の一部を頂点とする凸多面体（平面では凸多角形）となります。凸包の頂点となるのは、集合内の他の点の凸結合では表せない点です。

カラテオドリの定理によれば、N次元空間における集合の凸包を考える際、凸結合として考慮する点の数は、高々N+1個で十分です。例えば、平面（2次元）の点集合の凸包は、高々3点の凸結合、すなわち三角形の合併として表現できることが示唆されます。

平面上の有限点集合の場合、凸包はその最も外側の点を結ぶ多角形になり、これは最も左にある点から最も右にある点までを結ぶ「上包（upper hull）」と「下包（lower hull）」という二つの多角形の鎖に分けて考えることができます。

計算

計算幾何学の分野では、有限個の点集合の凸包を効率的に計算するアルゴリズムが研究されています。これらのアルゴリズムは、入力される点の数と、実際に凸包の頂点となる点の数によって計算量が評価されます。二次元や三次元においては、点の数に対して効率の良いアルゴリズムが開発されています。

他の概念との関係と応用

凸包は、ミンコフスキー和という集合の演算と興味深い関係があります。二つの集合のミンコフスキー和の凸包は、それぞれの集合の凸包のミンコフスキー和に等しくなります。これは、凸包をとる操作とミンコフスキー和が「交換可能」であることを意味します。

また、点の集合のドロネイ三角形分割やヴォロノイ図といった幾何構造とも関連が深く、特にドロネイ三角形分割は高次元空間における凸包の射影として捉えることができます。

位相的な性質としては、開集合の凸包は開集合に、コンパクト集合の凸包はコンパクト集合になりますが、閉集合の凸包が必ずしも閉集合になるとは限りません。

凸包を求める問題は、パターン認識、画像処理、統計学、地理情報システム (GIS)、計算幾何学の他のアルゴリズムの一部など、様々な分野で応用されています。

関連項目

アフィン包
線型包
ミンコフスキー和
ドロネイ三角形分割
ヴォロノイ図
* カラテオドリの定理

もう一度検索