凸包まとめ - junologyのブログ

凸包についてまとめてみたくなった。

実線形空間 $V$ の部分集合 $C$ が凸であるとは、任意の $a,b\in C$ と任意の実数 $0\le t\le 1$ に対して、 $(1-t)a+tb\in C$ であることだった。
さて、 $A\subset V$ が凸でなくても、 $A$ を含む $V$ の凸集合というものを考えることができる。
今回問題にするのは、そのような凸集合の中でも最小のもの「凸包」

新しい発見とか無いけれど、きっと1ヶ月後には忘れるだろうから、メモ。

凸包の定義などなど

まずは凸包を定義しないと始まらないが、できれば構成的な定義が良い。
実際に集合が「決定できる」かはともかくとして。

定義
$V$ を実線形空間、 $A\subset V$ を任意の部分集合とする。
$\mathrm{conv}(A)=\left\{\sum_{k=0}^n t_k a_k\,\mid\,n\in\mathbb{N},\,a_0,\dots,a_n\in A,\,t_k\ge 0,\,\sum_{k=0}^n t_k=1\right\}$
を $A$ の凸包という。

名前から当然期待されることだけれど、凸包は次の性質を持っている。

命題1
$V$ を実線形空間、 $A\subset V$ を任意の部分集合とする。

$\mathrm{conv}(A)$ は $V$ の凸集合

$A$ を含む $V$ の任意の凸集合は $\mathrm{conv}(A)$ を含む

（証明：１）
任意に $\textstyle\sum_{k=0}^m r_k a_k, \sum_{l=0}^n s_l b_l\in\mathrm{conv}(A)$ を取る。
ただし、
$a_k,b_l\in A,\,r_k,s_l\ge 0,\,\sum_{k=0}^m r_k = \sum_{l=0}^n s_l = 1$
である。
このとき、任意の $0\le t\le 1$ に対して、
$(1-t)r_k,\,ts_l\ge 0,\,\sum_{k=1}^m (1-t)r_k+\sum_{l=1}^n ts_l = (1-t)+t=1$
∴ $(1-t)\sum_{k=0}^m r_k a_k + t\sum_{l=0}^n s_l b_l \in\mathrm{conv}(A)$

（証明：２）
$C$ を $A$ を含む任意の凸集合とする。
$n\in\mathbb{N}$ に関する帰納法によって、次の形の元が $C$ に含まれることを示す。
$\sum_{k=0}^n t_k a_k\quad\text{(}a_k\in A,\,t_k\ge 0,\,\sum_{k=0}^n t_k = 1\text{)}$ … （＊）
$n=0$ の時、上は $a_0\in A$ なので、勿論 $a_0\in C$
$0\le m < n$ なる $m$ について、（＊）の形の元が全て $C$ に含まれていたと仮定する。
もしも $t_n=1$ ならば $t_0=t_1=\dots =t_{n-1}=0$ なので、（＊）は $a_n$ であるから、それは $C$ に含まれる。
もしも $t_n<1$ ならば、帰納法の仮定より
$\sum_{k=0}^{n-1}\frac{t_k}{1-t_n} a_k\in C$
また、 $C$ は $A$ を含むので、 $a_n\in C$ であり、 $C$ は凸集合であることより
$\sum_{k=0}^n t_k a_k = (1-t_n)\sum_{k=0}^{n-1}\frac{t_k}{1-t_n} a_k + t_n a_n\in C$
よって、 $C$ は（＊）の形の元を全て含む。
（証明終）

命題1-2は、「 $A$ を含む最小の凸集合が唯一存在」することを示している。
つまり、 $\mathrm{conv}(A)$ の定義として、「 $A$ を含む最小の凸集合」を採用しても良い。

さらにいえば、
$\mathrm{conv}(A)=\bigcap C\quad$ （ただし、 $C$ は $A$ を含む全ての凸集合をわたる）
である。
右辺は「凸集合同士の共通部分は凸集合」であるという、ほぼ自明な事実から凸集合であり、またその最小性は明らかである。
よって、命題1-2 よりこの等式が得られる。
この辺の議論は、閉包に対するいくつかの定義を比べているのに似ている。

凸包はいくつの点で決定できるか？

上で定義した凸包だが、特に $V$ が有限次元の場合には、 $\mathrm{conv}(A)$ を決定する際に、頂点として $A$ の元をやたらに多く取り出しても仕方がないだろう、という予想がつく。
では、いくつの点を取り出して調べれば良いか。
$\mathbb{R}^n$ において、異なる $n+1$ 点の凸包（n-単体）が内部を持つことに注意すると、次の命題が予想される。

命題2
$V$ を $n$ 次元実線形空間とすると、任意の $A\subset V$ について
$\mathrm{conv}(A)=\left\{\sum_{k=0}^n t_k a_k\,\mid\,a_k\in A,\,t_k\ge 0,\,\sum_{k=0}^nt_k=1\right\}$

（証明）
右辺= $C$ とおく。
$\mathrm{conv}(A)\supset C$ は明かなので、逆の包含を示す。
任意に $x=\textstyle\sum_{k=0}^{r}t_k a_k\in\mathrm{conv}(A)$ をとる。
もしも $r\le n$ ならば、定義より $x\in C$ 。
一方 $r\ge n+1$ の時、少くとも1つが 0 でない実数の組 $\lambda_1,\dots,\lambda_r$ があって
$\sum_{k=1}^r \lambda_k (a_k-a_0)=0$
とできる。
$\textstyle\lambda_0= -\sum_{k=1}^r \lambda_k$ とおくと、
$\sum_{k=0}^r \lambda_k a_k = 0\,,\quad \sum_{k=0}^r\lambda_k = 0$
ここで、 $0,\dots,r$ の順番を適当に入れかえて、 $\lambda_r\neq 0$ かつ、
$\frac{t_r}{\lambda_r} = \min\left\{\frac{t_k}{\lambda_k}\,\mid\,\lambda_k\neq 0\right\}$
であると仮定しても良く、この時
$x=\sum_{k=0}^r t_k a_k=\sum_{k=0}^r t_k a_k - \frac{t_r}{\lambda_r}\sum_{k=0}^r \lambda_k a_k =\sum_{k=0}^{r-1}\left(t_k-\frac{t_r}{\lambda_r}\lambda_k\right) a_k$
$\sum_{k=0}^{r-1}\left(t_k-\frac{t_r}{\lambda_r}\lambda_k\right) = \sum_{k=0}^r t_k - \frac{t_r}{\lambda_r}\sum_{k=0}^r \lambda_k = 1 - 0 = 1$
$0\le\forall k\le (r-1)\,:\,\left(t_k-\frac{t_r}{\lambda_r}\lambda_k\right)\ge 0$
これを繰り返すことで、 $a_0,\dots,a_r$ を適当に並びかえた上で、ある $\tau_0,\dots,\tau_n\ge 0$ によって、
$x=\sum_{k=0}^r t_k a_k=\sum_{k=0}^n\tau_k a_k\,,\quad \sum_{k=0}^n\tau_k=1$
とできる。
よって、 $x\in C$
（証明終）

命題2によって、有限次元においての凸包が理解しやすいものになった。
特に、記号の上ではとても簡単に記述できる。
実線形空間 $V$ の部分集合 $A,B\subset V$ と実数 $r\in\mathbb{R}$ に対して
$A+B=\left\{a+b\,\mid\,a\in A,\,b\in B\right\}$
$rA=\left\{ra\,\mid\, a\in A$
という記号を導入する。
$n\ge 0$ に対して、
$\Delta^n=\left\{(t_0,\dots,t_n)\in\mathbb{R}^{n+1}\,\mid\, t_k\ge 0,\,\sum_{k=0}^n t_k=1\right\}$
とおくと、 $\mathrm{dim} V=n<\infty$ ならば、命題2によって
$\mathrm{conv}(A)=\quad\sum_{(t_0,\dots,t_n)\in\Delta^n} \left(t_0 A+\dots+t_n A\right)$
と書ける。

凸包と位相

以下、 $V$ はHausdorffな実位相線形空間とする。
つまり、 $V$ はHausdorffな位相を持つ実線形空間であり、和 $V\times V\ni (u,v)\mapsto u+v\in V$ および実数倍 $\mathbb{R}\times V\ni (r,v)\mapsto rv\in V$ は連続であるとする。
この時、 $A$ の位相的な性質と、その凸包 $\mathrm{conv}(A)$ の位相的な性質がどのように関係しているか調べる。
位相線形空間の性質は別の機会にまとめるとして、基本的な事実を次に挙げる。

事実
位相線形空間 $V$ について、

$r\in\mathbb{R}\setminus\{0\}$ について、 $V\ni v\to rv\in V$ は同相写像

和 $V\times V\to V$ は開写像

この事実をもとに、次がわかる。

命題3
$A\subset V$ について

$A$ が開ならば、 $\mathrm{conv}(A)$ も開

$V$ が有限次元の時、 $A$ がコンパクトならば、 $\mathrm{conv}(A)$ もコンパクト

（証明：１）
任意に $x=\textstyle\sum_{k=1}^n t_k a_k\in\mathrm{conv}(A)$ をとる。
ただし、
$a_k\in A,\,t_k> 0,\,\sum_{k=1}^n t_k = 1$
とする（ $t_k=0$ であるような $k$ を除けば良い）。
$A$ が開であることから、 $t_k A$ も開である。
さらに、和が開写像であることより $U=\textstyle\sum_{k=1}^n t_kA$ も開である。
明らかに $U$ は $x$ を含み $\mathrm{conv}(A)$ に含まれる。
よって $x$ は $\mathrm{conv}(A)$ の内点であり、 $x\in\mathrm{conv}(A)$ は任意だったので、 $\mathrm{conv}(A)$ は開。

（証明：２）
$\mathrm{dim} V=n<\infty$ とする。
写像 $f:\mathbb{R}^{n+1}\times V^{\oplus(n+1)}\to V$ を次で定義する。
$f(t_0,\dots,t_n,v_0,\dots,v_n)=\sum_{k=0}^n t_k v_k$
$f$ は連続である。
すると
$\mathrm{conv}(A)=f\left(\Delta^n\times \underset{n\text{times}}{A\times\dots\times A}\right)$
はコンパクト集合の像なので、コンパクト。
（証明終）

命題3に関して、 $A\subset V$ が閉集合でも $\mathrm{conv}(A)$ が閉とは限らない。
例えば、 $V=\mathbb{R}^2$ において、 $A=\{0\}\times[0,1]\cup\mathbb{R}\times\{0\}$ は閉集合だが
$\mathrm{conv}(A)=\mathbb{R}\times[0,1)\cup\{(0,1)\}$
は閉でない。

凸包の直径（2013/01/15 追記）

前節では $V$ が実位相線形空間の場合を考察したが、この節では、さらに仮定を足して $V$ がノルム空間である場合を考える。
ノルム空間は実位相線形空間なので、前節の結果は全てこの場合でも成立する。

ノルム空間は距離空間なので、通常の距離空間と同じように、有界な部分集合 $A\subset V$ に対して次のようにその「直径」を定義できる。
$\mathrm{diam}(A)=\sup_{x,y\in A}\left\|x-y\right\|$
この節の主題は $\mathrm{diam}(\mathrm{conv}(A))$ について考察することである。

補題4
$V$ をノルム空間とする。
任意の点 $x\in V$ と $r>0$ に対して、以下の集合は凸。
$B(x;r)=\left\{y\in V\,\mid\,\left\|y-x\right\| < r\right\}$
$\bar{B}(x;r)=\left\{y\in V\,\mid\,\left\|y-x\right\|\le r\right\}$

上の議論で $<$ を $\le$ に置き換えれば、同様にして $\bar{B}(x;r)$ も凸。
（証明終）

ノルム空間における凸包で距離の議論をする上では、この補題4と命題1の組み合わせが便利。

命題5
$V$ をノルム空間とする。
任意の有界集合 $A\subset V$ に対して、次の等式が成立する。
$\mathrm{diam}(A)=\mathrm{diam}(\mathrm{conv}(A))$

（証明）
$A\subset\mathrm{conv}(A)$ なので、直径の定義から
$\mathrm{diam}(A)\le\mathrm{diam}(\mathrm{conv}(A))$
は明らかなので、逆の不等式を示す。

任意に $x,x'\in\mathrm{conv}(A)$ をとる。
凸包の定義から $a_1,\dots,a_m,a'_1,\dots,a'_n\in A$ と $t_1,\dots,t_m,t'_1,\dots,t'_n\ge0$ が存在して
$x=\sum_{k=1}^m t_ka_k\quad,\qquad y=\sum_{l=1}^n t'_la'_l$
$\sum_{k=1}^m t_k=\sum_{l=1}^n t'_l = 1$
が成立するようにできる。
特に、必要なら係数 $0$ で項を追加することによって $m=n\ge 2$ かつ $a_k=a'_k,\,k=1,\dots n$ として良い。
$S=\{a_1,\dots,a_n\}$ とおく。
$x,x'\in\mathrm{conv}(S)$ である。
$\rho=\max_{1\le k < l\le n}\left\|a_k-a_l\right\|$
とおく。
$a_1,\dots,a_n\in A$ なので $\rho\le\mathrm{conv}(A)$ であることに注意する。

各 $1\le k\le n$ について、 $\rho$ の定義より
$S\subset\bar{B}(a_k;\rho)$
であるが、命題4より、この右辺は凸なので、命題1より
$\mathrm{S}\subset\bar{B}(a_k;\rho)$
$x\in\mathrm{S}$ だったので、つまり $\left\|x-a_k\right\|\le\rho$ .
このことよりさらに
$S\subset\bar{B}(x;\rho)$
だから、
$x'\in\mathrm{conv}(S)\subset\bar{B}(x;\rho)$
従って
$\left\|x-x'\right\|\le\rho\le\mathrm{diam}(A)$

以上より
$\mathrm{diam}(\mathrm{conv}(A))\le\mathrm{diam}(A)$
で逆の不等式が示せた。
（証明終）