凸包

赤で表される集合の凸包は、青で表された凸集合である。

数学における凸包（とつほう、英: convex hull）または凸包絡（とつほうらく、英: convex envelope）は、与えられた集合を含む最小の凸集合である。例えば X がユークリッド平面内の有界な点集合のとき、その凸包は直観的には X を輪ゴムで囲んだときに輪ゴムが作る図形として視認することができる[1]。

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

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

「凸集合」および「凸結合」も参照

定理

与えられた点集合が凸集合であるとは、その集合に属する点の任意の対を結ぶ線分がその集合に含まれることを言うのであった。与えられた集合 X に対して、その凸包は以下の同値な条件：

  1. X を含む（唯一の）最小の凸集合、
  2. X を含む凸集合全ての交わり、
  3. X に属する点から得られる凸結合全体の成す集合、
  4. 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 ⊆ Conv ⁡ ( X ) . {\displaystyle X\subseteq \operatorname {Conv} (X).}
  • 凸包作用素は「単調性」を持つ。即ち、二つの集合 X, Y が X ⊆ Y を満たすならば、X の凸包は Y の凸包に含まれる: X ⊆ Y ⟹ Conv ⁡ ( X ) ⊆ Conv ⁡ ( Y ) . {\displaystyle X\subseteq Y\implies \operatorname {Conv} (X)\subseteq \operatorname {Conv} (Y).}
  • 凸包作用素は「冪等性」を持つ。即ち、任意の X に対して X の凸包の凸包は X の凸包に等しい: Conv ⁡ ( Conv ⁡ ( X ) ) = Conv ⁡ ( X ) . {\displaystyle \operatorname {Conv} (\operatorname {Conv} (X))=\operatorname {Conv} (X).}

を満たす。

有限点集合の凸包

平面上での、いくつかの点に対する凸包

有限な点集合の凸包は、それに属する点から得られる凸結合全体の成す集合である。凸結合における S の各点 xi に掛かる重みあるいは係数 αi は、全て正かつそれらの総和が 1 となるものであり、これらの重みは点の間の重み付き平均の計算に用いられる。このような係数の組を選ぶごとに凸包に属する点が一つ定まり、係数として可能な全ての組を考えることによって凸包の全体が得られる。式にすれば、凸包は

{ ∑ i = 1 | S | α i x i | ( ∀ i : α i ≥ 0 ) ∧ ∑ i = 1 | S | α i = 1 } {\displaystyle \left\{\sum _{i=1}^{|S|}\alpha _{i}x_{i}{\mathrel {\;{\Bigg |}\;}}(\forall i:\alpha _{i}\geq 0)\wedge \sum _{i=1}^{|S|}\alpha _{i}=1\right\}}

で与えられる集合ということになる。Rn 内の有限点集合 S の凸包は、平面の場合は凸多角形、三次元空間の場合は凸多面体、より一般の次元では凸超多面体（英語版）または凸多胞体[注釈 1]）と呼ばれる。S の点 xi でそれ以外の点の凸包に属さないもの ( x i ∉ Conv ⁡ ( S ∖ { x i } {\displaystyle x_{i}\notin \operatorname {Conv} (S\setminus \{x_{i}\}} ) を Conv(S) の頂点と呼ぶ。実は Rn の任意の凸多面体は、その頂点集合の凸包になっている。

有限集合の凸包は輪ゴムを掛けるようなものである

S の点が全て一つの直線上に載っているならば、S の凸包はもっとも外側にある二点を結ぶ線分になる。また、集合 S が平面上の（つまり二次元の）空でない有限部分集合のとき、S 全体をゴムバンドでぐるりと囲んでから、これを放して縮まる状況を想像すると、ゴムバンドがピンと張った状況で S の凸包を見取ることができる[1]。

二次元において、凸包は最左点と最右点の間を引き延ばしてできる「上包」(upper hull) と「下包」(lower hull) と呼ばれる二つの多角形の鎖に分けることがある。より一般に言えば、任意次元で一般の位置にある点の集合に対して、凸包の各刻面（英語版）は（凸包とその直上の点を分離することで）上方または下方に向き付けられる。上方を向く刻面全ての合併が上包と呼ばれる位相的円板を成すのである。同様に下包は下方向き刻面全体の合併を言う[3]

凸包の計算

詳細は「凸包アルゴリズム」を参照
「ギフト包装法」も参照

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

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

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

ミンコフスキー和と凸包

「ミンコフスキー算（英語版）」および「シャプレー-フォークマンの補題（英語版）」も参照
集合のミンコフスキー和: 二つの正方形 Q1 = [0,1]2 と Q2 = [1,2]2 のミンコフスキー和はQ1+Q2 = [1,3]2 なる正方形である

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

ミンコフスキー和
実線型空間において、二つの空でない集合 S1, S2 のミンコフスキー和 S1 + S2 は、加えられる各集合の元ごとの和の集合
S 1 + S 2 = { x 1 + x 2 : x 1 ∈ S 1 ∧ x 2 ∈ S 2 } {\displaystyle S_{1}+S_{2}=\{x_{1}+x_{2}:x_{1}\in S_{1}\land x_{2}\in S_{2}\}}
として定義される。より一般に、空でない部分集合の有限族 Si (i = 1, 2, …, n) のミンコフスキー和は、同様に元ごとの和をとって
∑ i = 1 n S i := { ∑ i = 1 n x i : x i ∈ S i } {\displaystyle \sum _{i=1}^{n}S_{i}:=\left\{\sum _{i=1}^{n}x_{i}:x_{i}\in S_{i}\right\}}
で与えられる。ミンコフスキー和に関して、零ベクトルのみからなる自明空間 {0} は単位元、空集合 ∅ は吸収元を成す。

実線型空間の任意の二つの部分集合 S1, S2 に対して、それらのミンコフスキー和の凸包はそれぞれの凸包のミンコフスキー和に等しい。即ち

Conv ⁡ ( S 1 + S 2 ) = Conv ⁡ ( S 1 ) + Conv ⁡ ( S 2 ) {\displaystyle \operatorname {Conv} (S_{1}+S_{2})=\operatorname {Conv} (S_{1})+\operatorname {Conv} (S_{2})}

が成り立つ。この結果は部分集合の有限族に対しても一般化できて、

Conv ( ∑ i = 1 n S i ) = ∑ i = 1 n Conv ⁡ ( S i ) {\displaystyle \operatorname {Conv} \!{\big (}\sum _{i=1}^{n}S_{i}{\bigr )}=\sum _{i=1}^{n}\operatorname {Conv} (S_{i})}

が成り立つ。言葉を替えれば、ミンコフスキー和作用素と凸包作用素は可換なのである[5][注釈 2]。

これらの結果は「ミンコフスキー和」が集合論的な和（合併）との違いを示すものになっている。実際、二つの凸集合の合併は必ずしも凸でなく、包含関係 Conv(S) ∪ Conv(T) ⊆ Conv(S ∪ T) は一般には真の包含になる。凸部分集合全体の成す集合を（完備な）束とするのに凸包作用素は重要で、通例この束における結び演算（英語版） (join) ∨ は二つの凸集合の合併の凸包

Conv ⁡ ( S ) ∨ Conv ⁡ ( T ) := Conv ⁡ ( S ∪ T ) = Conv ⁡ ( Conv ⁡ ( S ) ∪ Conv ⁡ ( T ) ) {\displaystyle \operatorname {Conv} (S)\vee \operatorname {Conv} (T):=\operatorname {Conv} (S\cup T)=\operatorname {Conv} (\operatorname {Conv} (S)\cup \operatorname {Conv} (T))}

によって与えられる。

他の構造との関係

点集合のドロネイ三角形分割とその双対であるヴォロノイ図は数学的に凸包と関係がある。Rn におけるドロネイ三角形分割は、Rn+1 における凸包の射影と見做すことができる[6]。

位相的には、開集合の凸包は常にそれ自身開であり、コンパクト集合の凸包は常にそれ自身コンパクトとなるが、閉集合の凸包で閉とならないものが存在する[7]。例えば、閉集合

{ ( x , y ) ∣ y ≥ 1 1 + x 2 } {\displaystyle \left\{(x,y)\mid y\geq {\frac {1}{1+x^{2}}}\right\}}

の凸包は開上半平面になる。

応用

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

脚注

注釈

  1. ^ 多胞体を四次元の場合に限って用いる流儀もある。また、三次元も含めた一般の次元において単に凸多面体と呼ぶ流儀もある
  2. ^ ミンコフスキー和と凸包の可換性については (Schneider 1993, pp. 2–3, Theorem 1.1.2) を見よ。同文献はミンコフスキー和の凸包に関して "Chapter 3 Minkowski addition" (pp. 126–196) でより詳しく議論している。

出典

  1. ^ a b de Berg et al. 2000, p. 3.
  2. ^ Knuth 1992.
  3. ^ de Berg et al. 2000, p. 6—凸包を二つに分けるアイデアは Andrew (1979) によるグラハム探索（英語版）の効率化版に由来する。
  4. ^ Chazelle 1993.
  5. ^ Krein & Šmulian 1940, pp. 562–563, Theorem 3.
  6. ^ Brown 1979.
  7. ^ Grünbaum 2003, p. 16.

参考文献

  • Andrew, A. M. (1979), “Another efficient algorithm for convex hulls in two dimensions”, Information Processing Letters 9 (5): 216–219, doi:10.1016/0020-0190(79)90072-3 .
  • Brown, K. Q. (1979), “Voronoi diagrams from convex hulls”, Information Processing Letters 9 (5): 223–228, doi:10.1016/0020-0190(79)90074-7 .
  • de Berg, M.; van Kreveld, M.; Overmars, Mark; Schwarzkopf, O. (2000), Computational Geometry: Algorithms and Applications, Springer, pp. 2–8, https://books.google.co.jp/books?id=tkyG8W2163YC&pg=PA2&redir_esc=y&hl=ja .
  • Chazelle, Bernard (1993), “An optimal convex hull algorithm in any fixed dimension” (PDF), Discrete and Computational Geometry 10 (1): 377–409, doi:10.1007/BF02573985, http://www.cs.princeton.edu/~chazelle/pubs/ConvexHullAlgorithm.pdf .
  • Grünbaum, Branko (2003), Convex Polytopes, Graduate Texts in Mathematics (2nd ed.), Springer, ISBN 9780387004242 .
  • Knuth, Donald E. (1992), Axioms and hulls, Lecture Notes in Computer Science, 606, Heidelberg: Springer-Verlag, p. ix+109, doi:10.1007/3-540-55611-7, ISBN 3-540-55611-7, MR1226891, http://www-cs-faculty.stanford.edu/~uno/aah.html .
  • Krein, M.; Šmulian, V. (1940), “On regularly convex sets in the space conjugate to a Banach space”, Annals of Mathematics, 2nd ser. 41: 556–583, doi:10.2307/1968735, JSTOR 1968735, MR2009, https://jstor.org/stable/1968735 .
  • Schneider, Rolf (1993), Convex bodies: The Brunn–Minkowski theory, Encyclopedia of Mathematics and its Applications, 44, Cambridge: Cambridge University Press, ISBN 0-521-35220-7, MR1216521 .

関連項目

外部リンク

  • Weisstein, Eric W. "Convex Hull". mathworld.wolfram.com (英語).
  • Hazewinkel, Michiel, ed. (2001), “Convex hull”, Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4, https://www.encyclopediaofmath.org/index.php?title=Convex_hull 
  • "Convex Hull" by Eric W. Weisstein, Wolfram Demonstrations Project, 2007.