凸包のソースを表示

[[File:Extreme points.svg|thumb|right|赤で表される集合の凸包は、青で表された[[凸集合]]である。]]
[[数学]]における'''凸包'''（とつほう、{{lang-en-short|''convex hull''}}）または'''凸包絡'''（とつほうらく、{{lang-en-short|''convex envelope''}}）は、与えられた集合を含む最小の[[凸集合]]である。例えば {{mvar|X}} が[[ユークリッド平面]]内の有界な点集合のとき、その凸包は直観的には {{mvar|X}} を輪ゴムで囲んだときに輪ゴムが作る図形として視認することができる{{sfn|de Berg|van Kreveld|Overmars|Schwarzkopf|2000|p=3}}。

精確に言えば、{{mvar|X}} の凸包は {{mvar|X}} を含む全ての凸集合の交わり、あるいは同じことだが {{mvar|X}} に属する点の[[凸結合]]全体の成す集合として定義される。後者の定式化であれば、凸包をユークリッド空間だけでなく任意の[[実線型空間]]や、より一般に{{ill2|有向マトロイド|en|Oriented matroid}}に対して考えることができる{{sfn|Knuth|1992}}。

平面上あるいは低次元ユークリッド空間内の有限点集合に対してその凸包を計算する[[アルゴリズム]]問題は、[[計算幾何学]]の基本的問題の一つである。

{{See also|凸集合|凸結合}}

== 定理 ==
与えられた点集合が[[凸集合]]であるとは、その集合に属する点の任意の対を結ぶ線分がその集合に含まれることを言うのであった。与えられた集合 {{mvar|X}} に対して、その'''凸包'''は以下の同値な条件：
# {{mvar|X}} を含む（唯一の）最小の凸集合、
# {{mvar|X}} を含む凸集合全ての交わり、
# {{mvar|X}} に属する点から得られる[[凸結合]]全体の成す集合、
# {{mvar|X}} に属する点を頂点とする[[単体 (数学)|単体]]全ての合併
の何れか一つ（従って全て）を満たす集合として定義される。

一つ目の定式化については、任意の {{mvar|X}} に対して実際に {{mvar|X}} を含む最小の凸集合が存在して一つに定まることはそのままでは明らかなことでない。しかし二つ目の定式化では、{{mvar|X}} を含む全ての凸集合の交わりは[[well-defined|明確に定まり]]（特に全体集合は凸であるから、これは空積にはならない）、かつこの交わりは（[[共通部分 (数学)|交わり]]の定義によって）{{mvar|X}} を含む任意の凸集合 ''Y'' に含まれるから、この交わりが {{mvar|X}} を含む唯一最小なる凸集合に他ならないことがわかる。

また、{{mvar|X}} を含む各凸集合は（それが凸であるという仮定によって）{{mvar|X}} に属する点の凸結合をすべて含むから、従ってこのような凸結合全体の成す集合は {{mvar|X}} を含む凸集合全ての交わりに含まれる。逆に、そのような凸結合全体の成す集合はそれ自身 {{mvar|X}} を含む凸集合ゆえ {{mvar|X}} を含む凸集合全ての交わりを含むから、これら二つの定式化が同じ集合を与えていることが知れる。

実は、[[凸包に関するカラテオドリの定理]]によれば、{{mvar|X}} が ''N''-次元線型空間の部分集合であるとき、凸包を求めるには上記定義において高々 ''N'' + 1 個の点の凸結合を考えれば十分である。従って特に、平面上の三点以上を含む集合の凸包は {{mvar|X}} に属する点の任意の三つ組から得られる[[三角形]]全てに亙る合併に一致し、同様により一般の ''N''-次元空間における凸包は {{mvar|X}} に属する高々 ''N'' + 1 点を頂点として定まる[[単体 (数学)|単体]]全てに亙る合併に一致する。

{{mvar|X}} の凸包が[[閉集合]]となるとき（よくあるのが例えば {{mvar|X}} が[[有限集合]]やもっと一般に[[コンパクト集合]]のとき）、それは {{mvar|X}} を含む閉[[半空間]]全ての交わりと一致する。このとき、[[超平面分離定理]]は、凸包に属さない各点が半空間によって凸包と分離されることを保証する。しかし、このようなやり方で表すことのできない凸集合および凸包が存在する。例えばその一つは、その境界に一点しか含まない開半平面によって与えられる。

より抽象的に言えば、凸包をとる作用素 Conv() は[[閉包作用素]]を特徴づける三性質：
* 凸包作用素は「拡大性質」を持つ。即ち、任意の集合 {{mvar|X}} に対してその凸包は {{mvar|X}} を含む: <math>X\subseteq \operatorname{Conv}(X).</math>
* 凸包作用素は「[[単調写像|単調性]]」を持つ。即ち、二つの集合 ''X'', ''Y'' が ''X'' &sube; ''Y'' を満たすならば、{{mvar|X}} の凸包は ''Y'' の凸包に含まれる: <math>X\subseteq Y \implies \operatorname{Conv}(X)\subseteq \operatorname{Conv}(Y).</math>
* 凸包作用素は「[[冪等性]]」を持つ。即ち、任意の {{mvar|X}} に対して {{mvar|X}} の凸包の凸包は {{mvar|X}} の凸包に等しい: <math>\operatorname{Conv}(\operatorname{Conv}(X)) = \operatorname{Conv}(X).</math> 
を満たす。

== 有限点集合の凸包 ==
[[File:Convex hull.png|thumb|平面上での、いくつかの点に対する凸包]]

[[有限集合|有限]]な点集合の凸包は、それに属する点から得られる[[凸結合]]全体の成す集合である。凸結合における ''S'' の各点 ''x''<sub>''i''</sub> に掛かる重みあるいは係数 &alpha;<sub>''i''</sub> は、全て正かつそれらの総和が 1 となるものであり、これらの重みは点の間の[[重み付き平均]]の計算に用いられる。このような係数の組を選ぶごとに凸包に属する点が一つ定まり、係数として可能な全ての組を考えることによって凸包の全体が得られる。式にすれば、凸包は
:<math>\left\{\sum_{i=1}^{|S|} \alpha_i x_i \mathrel{\;\Bigg|\;} (\forall i: \alpha_i\ge 0)\wedge \sum_{i=1}^{|S|} \alpha_i=1 \right\}</math> 
で与えられる集合ということになる。'''R'''<sup>''n''</sup> 内の有限点集合 ''S'' の凸包は、平面の場合は[[凸多角形]]、三次元空間の場合は[[凸多面体]]、より一般の次元では{{ill2|凸ポリトープ|en|convex polytope|label=凸超多面体}}または凸多胞体{{efn|多胞体を四次元の場合に限って用いる流儀もある。また、三次元も含めた一般の次元において単に凸多面体と呼ぶ流儀もある}}）と呼ばれる。''S'' の点 ''x''<sub>''i''</sub> でそれ以外の点の凸包に属さないもの (<math>x_i \notin \operatorname{Conv}(S \setminus \{x_i \} </math>) を Conv(''S'') の[[頂点]]と呼ぶ。実は '''R'''<sup>''n''</sup> の任意の凸多面体は、その頂点集合の凸包になっている。

[[File:ConvexHull.svg|thumb|有限集合の凸包は輪ゴムを掛けるようなものである]]
''S'' の点が全て一つの[[直線]]上に載っているならば、''S'' の凸包はもっとも外側にある二点を結ぶ[[線分]]になる。また、集合 ''S'' が[[ユークリッド平面|平面]]上の（つまり二次元の）[[空集合|空]]でない[[有限集合|有限部分集合]]のとき、''S'' 全体を[[ゴムバンド]]でぐるりと囲んでから、これを放して縮まる状況を想像すると、ゴムバンドがピンと張った状況で ''S'' の凸包を見取ることができる{{sfn|de Berg|van Kreveld|Overmars|Schwarzkopf|2000|p=3}}。

二次元において、凸包は最左点と最右点の間を引き延ばしてできる「上包」(upper hull) と「下包」(lower hull) と呼ばれる二つの多角形の鎖に分けることがある。より一般に言えば、任意次元で一般の位置にある点の集合に対して、凸包の各{{仮リンク|刻面 (幾何学)|label=刻面|en|facet (mathematics)}}は（凸包とその直上の点を分離することで）上方または下方に向き付けられる。上方を向く刻面全ての合併が'''上包'''と呼ばれる位相的円板を成すのである。同様に'''下包'''は下方向き刻面全体の合併を言う{{sfn|de Berg|van Kreveld|Overmars|Schwarzkopf|2000|p=6|ps=&mdash;凸包を二つに分けるアイデアは {{harvtxt|Andrew|1979}} による{{仮リンク|グラハム探索|en|Graham scan}}の効率化版に由来する。}}

== 凸包の計算 ==
{{Main|[[凸包アルゴリズム]]}}
{{See also|ギフト包装法}}

計算幾何学において、点やその他の幾何学的対象のなす有限集合の凸包を計算するアルゴリズムが数多く知られている。[[ギフト包装法]]などがある。

「凸包の計算」というのは、曖昧さ無く効果的に求める凸図形を[[データ構造|表すデータ]]を構築することを意味する。凸包アルゴリズムの計算量は通例、入力点の数 ''n'' と凸包に属する点（出力点）の数 ''h'' とに関して評価される。

二次元及び三次元の点集合に対して、計算量 O(''n''&thinsp;log&thinsp;''h'') で凸包を計算できる[[出力依存アルゴリズム]]が知られている。三次元より高次の ''d''-次元では、凸包の計算時間は最悪の場合で <math>O(n^{\lfloor d/2\rfloor})</math> となる{{sfn|Chazelle|1993}}。

== ミンコフスキー和と凸包 ==
{{See also|{{仮リンク|ミンコフスキー算|en|Minkowski addition}}|{{仮リンク|シャプレー-フォークマンの補題|en|Shapley–Folkman lemma}}}}
[[File:Minkowski sum.png|thumb|集合の[[ミンコフスキー和]]: 二つの正方形 {{math|Q<sub>1</sub> {{=}} [0,1]<sup>2</sup>}} と {{math|Q<sub>2</sub> {{=}} [1,2]<sup>2</sup>}} のミンコフスキー和は{{math|Q<sub>1</sub>+Q<sub>2</sub> {{=}} [1,3]<sup>2</sup>}} なる正方形である]]

凸包を取る操作は集合のミンコフスキー和に関してよく振る舞う。

; ミンコフスキー和: 実線型空間において、二つの空でない集合 {{math|''S''<sub>1</sub>, ''S''<sub>2</sub>}} の[[ミンコフスキー和]] {{math|''S''<sub>1</sub> + ''S''<sub>2</sub>}} は、加えられる各集合の[[元ごとの和の集合]]<div style="margin: 1ex 2em"><math>
 S_1+S_2 = \{x_1+x_2 : x_1 \in S_1 \land x_2\in S_2\}
</math></div>として定義される。より一般に、空でない部分集合の有限族 {{math|1=''S''<sub>''i''</sub> (''i'' = 1, 2, …, ''n'')}} のミンコフスキー和は、同様に元ごとの和をとって<div style="margin: 1ex 2em"><math>
 \sum_{i=1}^n S_i := \left\{\sum_{i=1}^n x_i : x_i \in S_i\right\}
</math></div>で与えられる。ミンコフスキー和に関して、零ベクトルのみからなる自明空間 {{math|{0}}} は[[単位元]]、空集合 {{math|&empty;}} は[[吸収元]]を成す。

実線型空間の任意の二つの部分集合 {{math|''S''<sub>1</sub>, ''S''<sub>2</sub>}} に対して、それらのミンコフスキー和の凸包はそれぞれの凸包のミンコフスキー和に等しい。即ち
: <math>\operatorname{Conv}(S_1 + S_2) = \operatorname{Conv}(S_1) + \operatorname{Conv}(S_2)</math>
が成り立つ。この結果は部分集合の有限族に対しても一般化できて、
: <math>\operatorname{Conv}\!\big(\sum_{i=1}^n S_i\bigr) = \sum_{i=1}^n \operatorname{Conv}(S_i)</math>
が成り立つ。言葉を替えれば、ミンコフスキー和作用素と凸包作用素は[[交換法則|可換]]なのである{{sfn|Krein|Šmulian|1940|loc= Theorem 3 | pp=562–563}}{{efn|name="Schneider"|ミンコフスキー和と凸包の可換性については {{harv|Schneider|1993|loc= Theorem 1.1.2 |pp=2–3}} を見よ。同文献はミンコフスキー和の凸包に関して "Chapter&nbsp;3 Minkowski addition" (pp. 126–196) でより詳しく議論している。}}。

これらの結果は「ミンコフスキー和」が[[合併 (集合論)|集合論的な和]]（合併）との違いを示すものになっている。実際、二つの凸集合の合併は必ずしも凸でなく、[[包含関係]] {{math|Conv(''S'') ∪ Conv(''T'') ⊆ Conv(''S'' ∪ ''T'')}} は一般には真の包含になる。凸部分集合全体の成す集合を（[[完備束|完備]]な）[[束 (束論)|束]]とするのに凸包作用素は重要で、通例この束における{{仮リンク|束演算|label=結び演算|en|Join and meet}} (join) {{math|&or;}} は二つの凸集合の合併の凸包
: <math>\operatorname{Conv}(S)\vee \operatorname{Conv}(T) := \operatorname{Conv}(S\cup T) = \operatorname{Conv}(\operatorname{Conv}(S)\cup \operatorname{Conv}(T))</math>
によって与えられる。

== 他の構造との関係 ==
点集合の[[ドロネー図|ドロネイ三角形分割]]とその双対である[[ヴォロノイ図]]は数学的に凸包と関係がある。'''R'''<sup>''n''</sup> におけるドロネイ三角形分割は、'''R'''<sup>''n''+1</sup> における凸包の射影と見做すことができる{{sfn|Brown|1979}}。

位相的には、[[開集合]]の凸包は常にそれ自身開であり、[[コンパクト集合]]の凸包は常にそれ自身コンパクトとなるが、閉集合の凸包で閉とならないものが存在する{{sfn|Grünbaum|2003|p=16}}。例えば、閉集合
: <math>\left\{(x,y)\mid y\ge \frac{1}{1+x^2}\right\}</math>
の凸包は開[[上半平面]]になる。

== 応用 ==
凸包を求める問題の実用的な応用としては、[[パターン認識]]・[[画像処理]]・[[統計学]]・[[地理情報システム]]・[[抽象解釈]]による[[静的コード解析]]などがある。あるいはまた、点集合の[[幅]]や[[径]]を計算する[[回転キャリパー法]]のような、ほかの計算幾何学的アルゴリズムの構成部材としても重要な役割を提供する。

== 脚注 ==
=== 注釈 ===
{{notelist}}
=== 出典 ===
{{reflist|30em}}

== 参考文献 ==
*{{citation | last = Andrew | first = A. M. | doi = 10.1016/0020-0190(79)90072-3 | issue = 5 | journal = Information Processing Letters | pages = 216–219 | title = Another efficient algorithm for convex hulls in two dimensions | volume = 9 | year = 1979}}.
*{{citation | last = Brown | first = K. Q. | doi = 10.1016/0020-0190(79)90074-7 | issue = 5 | journal = Information Processing Letters | pages = 223–228 | title = Voronoi diagrams from convex hulls | volume = 9 | year = 1979}}.
*{{citation | last1 = de Berg | first1 = M. | last2 = van Kreveld | first2 = M. | last3 = Overmars | first3 = Mark | author3-link = Mark Overmars | last4 = Schwarzkopf | first4 = O. | pages = 2–8 | publisher = Springer | title = Computational Geometry: Algorithms and Applications | year = 2000 | url=https://books.google.co.jp/books?id=tkyG8W2163YC&pg=PA2&redir_esc=y&hl=ja}}.
*{{citation|first=Bernard|last=Chazelle|author-link=Bernard Chazelle|title=An optimal convex hull algorithm in any fixed dimension|journal=[[Discrete and Computational Geometry]]|volume=10|issue=1|pages=377–409|year=1993|doi=10.1007/BF02573985|url=http://www.cs.princeton.edu/~chazelle/pubs/ConvexHullAlgorithm.pdf|format=PDF}}.
*{{citation|title=Convex Polytopes|series=Graduate Texts in Mathematics|first=Branko|last=Grünbaum|authorlink=Branko Grünbaum|edition=2nd|publisher=Springer|year=2003|isbn=9780387004242}}.
*{{citation | last = Knuth | first = Donald E. | author-link = Donald Knuth | doi = 10.1007/3-540-55611-7 | isbn = 3-540-55611-7 | location = Heidelberg | mr = 1226891 | page = ix+109 | publisher = Springer-Verlag | series = Lecture Notes in Computer Science | title = Axioms and hulls | url = http://www-cs-faculty.stanford.edu/~uno/aah.html | volume = 606 | year = 1992}}.
*{{citation|first1=M.|last1=Krein|authorlink1=Mark Krein|first2=V.|last2=Šmulian|year=1940|title=On regularly convex sets in the space conjugate to a Banach space|journal=Annals of Mathematics|series=2nd ser.|volume=41|pages=556–583|jstor=1968735|doi=10.2307/1968735|mr=2009}}.
*{{citation|last=Schneider|first=Rolf|title=Convex bodies: The Brunn–Minkowski theory|series=Encyclopedia of Mathematics and its Applications|volume=44|publisher=Cambridge&nbsp;University Press|location=Cambridge|year=1993|isbn=0-521-35220-7|mr=1216521}}.

== 関連項目 ==
* [[アフィン包]]
* [[線型包]]
* [[クレイン＝ミルマンの定理]]
* {{仮リンク|ショケの定理|en|Choquet theory}}
* [[正則凸包]]
* {{仮リンク|直交凸包|en|Orthogonal convex hull}}
* {{仮リンク|オロイド|en|Oloid}}
* [[ヘリーの定理]]

== 外部リンク ==
* {{MathWorld|urlname=ConvexHull|title=Convex Hull}}
* {{SpringerEOM|urlname=Convex_hull|title=Convex hull}}
* [http://demonstrations.wolfram.com/ConvexHull/ "Convex Hull"] by [[Eric W. Weisstein]], [[Wolfram Demonstrations Project]], 2007.

{{デフォルトソート:とつほう}}
[[Category:閉包作用素]]
[[Category:凸包|*]]
[[Category:凸解析]]
[[Category:計算幾何学]]
[[Category:数学に関する記事]]