Carathéodoryの定理(凸幾何)
概要
Carathéodoryの定理(凸幾何)（Carathéodory's theorem）とは、$\mathbb{R}^n$ の部分集合 $S$ の凸包の任意の点は、$S$ の高々 $n+1$ 個の点の凸結合として書ける、という定理である。より強く、使う点をアフィン独立にとれ、$S$ が $d$ 次元のアフィン部分空間にあれば $d+1$ 個で足りることが、点がアフィン従属な限り係数の 1 つを $0$ に押し下げて点を減らす議論で示される。数 $n+1$ は単体の重心の例で減らせず、凸包は $S$ の点を頂点とする単体の和集合になる。コンパクト集合の凸包のコンパクト性の根拠であり、錐の形や色つきの形への一般化がある。
平面に有限個の点を打ち、その凸包（点を輪ゴムで囲んでできる凸多角形）の中に点 $x$ をとる。$x$ は打った点の重みつき平均（凸結合）で書けるが、点がいくつあっても、そのうちの 3 点だけ を使えば足りる。凸多角形を対角線で三角形に切り分ければ、$x$ はどれかの三角形に入り、その 3 頂点の凸結合になるからである。空間なら 4 点、一般に $\mathbb{R}^n$ なら $n+1$ 点で足りる。これが Carathéodory の定理 である。
この定理により、無限個の点を含みうる集合の凸包も、「高々 $n+1$ 点の凸結合」という有限の形で扱える。コンパクト集合の凸包がコンパクトであることの証明はこれに基づいており、Radonの定理(凸幾何) と同じく「$n+2$ 個の点のあいだには係数の和が $0$ の 1 次関係がある」ことから出る。この記事では、定理を「アフィン独立な点の凸結合で書ける」という強い形で証明し、$n+1$ が減らせないこと、錐の場合との関係、色つきの一般化を述べる。測度論の Carathéodoryの拡張定理 とは別の定理である。
定義
以下 $\mathbb{R}^n$ は $n$ 次元 Euclid空間 で、$e_1,\dots,e_n$ は標準基底、$a\cdot x$ は内積、$\|x\|$ は長さとする。点 $x_1,\dots,x_m$ の 凸結合 とは $\sum_i\lambda_ix_i$（$\lambda_i\ge0$、$\sum_i\lambda_i=1$）の形の点である。$S\subset\mathbb{R}^n$ の凸包 $\operatorname{conv}S$ は、$S$ を含む最小の凸集合であり、$S$ の有限個の点の凸結合全体の集合に等しい（凸集合 の定理「凸包と凸結合」）。
$x_0,\dots,x_k\in\mathbb{R}^n$ が アフィン独立（affinely independent）であるとは、差 $x_1-x_0,\dots,x_k-x_0$ が線形独立であることをいう。アフィン独立な点 $x_0,\dots,x_k$ の凸包を、$x_0,\dots,x_k$ を頂点とする $k$ 次元単体 という。
条件は次のように言い換えられる。実数 $\mu_0,\dots,\mu_k$ が $\sum_i\mu_ix_i=0$、$\sum_i\mu_i=0$ を満たせば、$\mu_0=-(\mu_1+\cdots+\mu_k)$ を代入して $\sum_{i\ge1}\mu_i(x_i-x_0)=0$ となり、逆も成り立つ。したがって、$x_0,\dots,x_k$ がアフィン独立であることは、
$$
\mu_0x_0+\cdots+\mu_kx_k=0,\quad\mu_0+\cdots+\mu_k=0\ \Longrightarrow\ \mu_0=\cdots=\mu_k=0
$$
と同値であり、点の並べ方によらない。この形の自明でない関係 $\mu$ を アフィン関係 と呼ぶ。これは アフィン部分空間 の記事のアフィン独立と同じ概念である。たとえば 2 点がアフィン独立であることは相異なることであり、平面の 3 点がアフィン独立であることは一直線上にないことである。1 次元単体は線分、2 次元単体は三角形、3 次元単体は四面体である。
アフィン独立な点の個数には上限がある。$x_0,\dots,x_k$ が $d$ 次元のアフィン部分空間 $a+U$（$U$ は $d$ 次元の部分空間）に含まれれば、差 $x_i-x_0$ は $U$ に属するので、それらが線形独立なら $k\le d$ である（基底と次元）。とくに $\mathbb{R}^n$ のアフィン独立な点は高々 $n+1$ 個である。
主定理
$x=\sum_{i=1}^m\lambda_ix_i$ を凸結合とし、すべての $\lambda_i$ は正で、$x_1,\dots,x_m$ はアフィン独立でないとする。このとき、ある $k$ について $x$ は $k$ 番目を除いた $m-1$ 個の点 $x_i$（$i\ne k$）の凸結合として書ける。
アフィン関係 $\mu=(\mu_1,\dots,\mu_m)$ をとる。$\mu$ は全部は $0$ でなく和が $0$ なので、$\mu_i>0$ となる $i$ がある。
$$
\tau:=\min\Bigl\{\frac{\lambda_i}{\mu_i}\Bigm|\mu_i>0\Bigr\}
$$
とおき、最小値をとる添字を $k$ とする。$\tau>0$ である。$\lambda_i':=\lambda_i-\tau\mu_i$ とおくと、$\mu_i\le0$ なら $\lambda_i'\ge\lambda_i>0$、$\mu_i>0$ なら $\tau$ の定め方から $\lambda_i'\ge0$ であり、$\lambda_k'=0$ である。さらに
$$
\sum_i\lambda_i'=\sum_i\lambda_i-\tau\sum_i\mu_i=1,\qquad\sum_i\lambda_i'x_i=\sum_i\lambda_ix_i-\tau\sum_i\mu_ix_i=x
$$
なので、$x=\sum_{i\ne k}\lambda_i'x_i$ は $x_i$（$i\ne k$）の凸結合である。$\square$
$S\subset\mathbb{R}^n$ とし、$x\in\operatorname{conv}S$ とする。このとき $x$ は、$S$ のアフィン独立な点の凸結合として書ける。とくに $x$ は $S$ の高々 $n+1$ 個の点の凸結合として書ける。さらに $S$ が $d$ 次元のアフィン部分空間に含まれるなら、高々 $d+1$ 個の点で足りる。
凸集合 の定理「凸包と凸結合」により、$x$ は $S$ の有限個の点の凸結合で書ける。そのような表し方のうち、点の個数 $m$ が最小のもの $x=\sum_{i=1}^m\lambda_ix_i$（$x_i\in S$）をとる。$\lambda_i=0$ の項を除けば個数が減るので、すべての $\lambda_i$ は正である。もし $x_1,\dots,x_m$ がアフィン独立でなければ、lem-ca-reduce により $x$ は $m-1$ 個の点の凸結合で書け、$m$ の最小性に反する。よって $x_1,\dots,x_m$ はアフィン独立である（とくに相異なる）。
アフィン独立な点の個数は、def-ca-affine の後で見たように、$\mathbb{R}^n$ では高々 $n+1$、$d$ 次元のアフィン部分空間の中では高々 $d+1$ である。$\square$
$S\subset\mathbb{R}^n$ について、$\operatorname{conv}S$ は、$S$ のアフィン独立な有限部分集合 $T$（高々 $n+1$ 点）を頂点とする単体 $\operatorname{conv}T$ すべての和集合に等しい。
$T\subset S$ なら $\operatorname{conv}T\subset\operatorname{conv}S$ なので、和集合は $\operatorname{conv}S$ に含まれる。逆の包含は thm-ca-main そのものである。$\square$
冒頭の平面の場合はこの系の $n=2$ にあたる。凸包の点は、$S$ の点を頂点とする三角形・線分・1 点のどれかに入る。三角形への切り分けを作らなくても、lem-ca-reduce の操作を繰り返すだけで、使う点を 3 個以下に減らせる。
例と反例
正方形の頂点 $v_1=(0,0)$、$v_2=(1,0)$、$v_3=(1,1)$、$v_4=(0,1)$ と、凸包の点 $x=\bigl(\tfrac12,\tfrac14\bigr)$ を考える。$x$ は 2 頂点の凸結合ではない。2 頂点を結ぶ線分は 4 辺と 2 本の対角線で、それぞれ $x_2=0$、$x_1=1$、$x_2=1$、$x_1=0$、$x_1=x_2$、$x_1+x_2=1$ の上にあるが、$x$ はどれも満たさない。一方で
$$
x=\tfrac12v_1+\tfrac14v_2+\tfrac14v_3=\tfrac14v_1+\tfrac12v_2+\tfrac14v_4
$$
であり、$x$ は 2 つの三角形 $v_1v_2v_3$ と $v_1v_2v_4$ のどちらの 3 頂点の凸結合にもなる。thm-ca-main は高々 $n+1=3$ 点で足りることを保証するが、使う点の選び方や係数は一つには決まらない。
単体 $\Delta_n:=\operatorname{conv}\{v_0,v_1,\dots,v_n\}$（$v_0=0$、$v_i=e_i$）の重心
$$
g:=\frac1{n+1}(v_0+v_1+\cdots+v_n)=\Bigl(\frac1{n+1},\dots,\frac1{n+1}\Bigr)
$$
は、$S=\{v_0,\dots,v_n\}$ の $n$ 個以下の点の凸結合では書けない。$n$ 個以下の点はある $v_k$ を含まない。$k\ge1$ なら、$v_k$ を除く頂点の凸結合は第 $k$ 座標が $0$ であり、$k=0$ なら、$v_0$ を除く頂点の凸結合は座標の和が $1$ である。$g$ の第 $k$ 座標は $\frac1{n+1}\ne0$、座標の和は $\frac n{n+1}\ne1$ なので、どちらでもない。$n=2$ では、三角形の重心は辺の上にない、ということである。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 使う点の個数が $n+1$ 以下（$n$ 以下に減らす） | 単体 $\Delta_n$ の頂点の集合と重心 | 決めた個数以下の点の凸結合で書けること |
| 空間が有限次元であること | 有限個の項を除いて $0$ である実数列の空間の $S=\{e_1,e_2,\dots\}$ | 決まった個数以下の点の凸結合で書けること |
| $x$ が $\operatorname{conv}S$ に属すること（閉包の点に広げる） | $\mathbb{R}^2$ の閉集合 $S=\{(t,0)\mid t\in\mathbb{R}\}\cup\{(0,1)\}$ と点 $(1,1)$ | $S$ の有限個の点の凸結合で書けること |
- 1 行目は ex-ca-sharp である。
- 有限個の項を除いて $0$ である実数列の全体 $V$ は実ベクトル空間で、凸結合と凸包は同じ式で定義できる。$e_i\in V$ を第 $i$ 項だけが $1$ の数列とし、$S=\{e_1,e_2,\dots\}$、$y_m:=\frac1m(e_1+\cdots+e_m)\in\operatorname{conv}S$ とおく。$y_m=\sum_j\lambda_je_{i_j}$（相異なる $i_j$）と書けば、$e_i$ は線形独立なので係数は座標で決まり、$\lambda$ が正である $e_i$ はちょうど $e_1,\dots,e_m$ である。よって $y_m$ を $S$ の点の凸結合で書くには $m$ 個の点が要る。$m$ は任意なので、個数の上限はない。
- 凸包 の例「反例：閉集合の凸包は閉とは限らない」により、$\operatorname{conv}S=\{(x,y)\mid0\le y< 1\}\cup\{(0,1)\}$ であり、$(1,1)$ はこれに属さないが、凸包の点 $\bigl(1,1-\frac1k\bigr)$ の極限である。したがって $(1,1)$ は凸包の閉包の点だが、$S$ の点の凸結合では書けない。
錐の形と持ち上げ
0 以上の係数の 1 次結合 $\sum_i\lambda_ix_i$（$\lambda_i\ge0$）を 錐結合 といい、$S$ の点の錐結合の全体を $\operatorname{cone}S$ と書く。凸錐 の定理「錐の Carathéodory の定理」は、$\operatorname{cone}S$ のどの点も $S$ の線形独立な点（したがって高々 $n$ 個）の錐結合で書けることを述べる。係数の和についての条件がない代わりに、アフィン独立が線形独立に、$n+1$ が $n$ に変わる。
2 つの形は、1 つ次元を上げると同じものになる。$\hat S:=\{(s,1)\mid s\in S\}\subset\mathbb{R}^{n+1}$ とおくと、$(x,1)=\sum_i\lambda_i(s_i,1)$（$\lambda_i\ge0$）の最後の成分は $\sum_i\lambda_i=1$ なので、
$$
x\in\operatorname{conv}S\iff(x,1)\in\operatorname{cone}\hat S
$$
であり、凸結合の係数と錐結合の係数は同じものである。さらに $(s_0,1),\dots,(s_k,1)$ が線形独立であることは、$s_0,\dots,s_k$ がアフィン独立であることと同値である（どちらも、$\sum_i\mu_is_i=0$、$\sum_i\mu_i=0$ から $\mu=0$ が出ることにあたる）。したがって、$\mathbb{R}^{n+1}$ での錐の Carathéodory の定理を $\hat S$ に使えば、thm-ca-main の前半がもう一度得られる。
応用
コンパクト集合の凸包
$S$ がコンパクトなら $\operatorname{conv}S$ もコンパクトである（凸包 の定理「コンパクト集合の凸包」）。thm-ca-main により、$\operatorname{conv}S$ はちょうど $n+1$ 個の項の凸結合（点の重複や係数 $0$ を許す）の全体なので、コンパクト集合 $S^{n+1}\times\{\lambda\in\mathbb{R}^{n+1}\mid\lambda_i\ge0,\ \sum_i\lambda_i=1\}$ の連続写像 $\bigl((s_i),\lambda\bigr)\mapsto\sum_i\lambda_is_i$ による像になるからである。項の個数に上限がなければ、凸包は「長さの決まらない凸結合」の和集合になり、この議論は使えない。
色つきの Carathéodory の定理
$n+1$ 個の集合 $S_0,\dots,S_n$ がそれぞれ点 $x$ を凸包に含むとき、各 $S_i$ から 1 点ずつ選んで、その $n+1$ 点の凸包に $x$ が入るようにできる。$S_i$ を $i$ 番目の色に塗った点の集合と思えば、「各色の点が $x$ を囲んでいれば、全部の色を 1 つずつ使った単体で $x$ を囲める」ということである。$S_0=\cdots=S_n=S$ とすると、thm-ca-main の「高々 $n+1$ 個」の部分になる。
$S_0,\dots,S_n\subset\mathbb{R}^n$ とし、点 $x$ がすべての $\operatorname{conv}S_i$ に属するとする。このとき $s_i\in S_i$（$i=0,\dots,n$）で、$x\in\operatorname{conv}\{s_0,\dots,s_n\}$ となるものがある。
平行移動して $x=0$ としてよい。thm-ca-main により、$0$ は各 $S_i$ の有限個の点の凸包に入るので、$S_i$ をその有限部分集合に取り替えて、$S_i$ は有限集合としてよい。
選び方 $t=(s_0,\dots,s_n)\in S_0\times\cdots\times S_n$ は有限個である。各 $t$ について $K_t:=\operatorname{conv}\{s_0,\dots,s_n\}$ は有限集合の凸包なのでコンパクトであり（凸包 の定理「コンパクト集合の凸包」）、連続関数 $\|y\|$ は $K_t$ 上で最小値 $d(t)$ をとる（コンパクト空間 の定理「最大値・最小値の存在」）。$d(t)$ が最小になる $t$ を選ぶ。$d(t)=0$ なら $0\in K_t$ で証明が終わるので、$d(t)>0$ と仮定して矛盾を導く。$K_t$ の点で $\|z\|=d(t)$ となるものを $z$ とする。$z\ne0$ である。
段 1：$y\in K_t$ なら $z\cdot y\ge\|z\|^2$ である。$0< u\le1$ について $z+u(y-z)\in K_t$ なので
$$
\|z\|^2\le\|z+u(y-z)\|^2=\|z\|^2+2u\,z\cdot(y-z)+u^2\|y-z\|^2
$$
であり、$u$ で割って $u\to0$ とすると $z\cdot(y-z)\ge0$ を得る。
段 2：ある $i$ について $z\in\operatorname{conv}\{s_j\mid j\ne i\}$ である。$z=\sum_j\lambda_js_j$（凸結合）と書くと、段 1 より $z\cdot s_j\ge\|z\|^2$ で、$\sum_j\lambda_j\,z\cdot s_j=z\cdot z=\|z\|^2$ なので、$\lambda_j>0$ となる $j$ ではすべて $z\cdot s_j=\|z\|^2$ である。ある $\lambda_i$ が $0$ ならその $i$ でよい。すべての $\lambda_j$ が正なら、$s_0,\dots,s_n$ はすべて超平面 $A:=\{y\mid z\cdot y=\|z\|^2\}$ に含まれる。$A$ は $n-1$ 次元のアフィン部分空間なので、thm-ca-main により $z$ は $s_0,\dots,s_n$ のうち高々 $n$ 個の点の凸結合で書け、使われない添字 $i$ がある。
段 3：$0\in\operatorname{conv}S_i$ なので、$z\cdot y\le0$ となる $y\in S_i$ がある（すべての $y\in S_i$ で $z\cdot y>0$ なら、$S_i$ の点の凸結合 $w$ でも $z\cdot w>0$ となり、$0$ がその凸結合であることに反する）。$t$ の $i$ 番目を $y$ に取り替えた選び方を $t'$ とすると、$K_{t'}$ は段 2 により $z$ を含み、$y$ も含むので、線分 $z+u(y-z)$（$0\le u\le1$）を含む。
$$
\|z+u(y-z)\|^2=\|z\|^2+2u\bigl(z\cdot y-\|z\|^2\bigr)+u^2\|y-z\|^2\le\|z\|^2-2u\|z\|^2+u^2\|y-z\|^2
$$
は、$0< u\le1$ かつ $u< 2\|z\|^2/\|y-z\|^2$ のとき $\|z\|^2$ より小さい（$z\cdot y\le0< \|z\|^2=z\cdot z$ なので $y\ne z$ である）。よって $d(t')< d(t)$ となり、$t$ の選び方に反する。$\square$
補足
E. Steinitz は Ste13 §10 で、凸包の解析的な表示として、有限個の点の錐結合で書ける $0$ でない点は、そのうち $n$ 個以下（点が $r$ 次元の部分空間にあれば $r$ 個以下）の点の錐結合で書けること（Satz 1、p. 153）、有限個の点の凸結合で書ける点は、点が $r$ 次元のアフィン部分空間にあれば $r+1$ 個以下の点の凸結合で書けること（Satz 2、pp. 153–154）、任意の集合の凸包の点が高々 $r+1$ 個の点の凸包に入ること（Satz 4、p. 155）を証明している。証明は prf-ca-reduce と同じく、1 次関係の定数倍を引いて係数を 1 つ $0$ にするものである。Steinitz は同じ論文（p. 130 の脚注）で、C. Carathéodory が凸な点集合についての基本的な定理を簡潔に述べていることに触れている。この定理は Carathéodory の名で呼ばれる。同じアフィン関係を符号で分ける議論からは Radonの定理(凸幾何) が、さらにそこから Hellyの定理 が得られる。
関連項目
- 前提: 凸集合, 凸包, 線形独立
- 比較: 凸錐, アフィン部分空間, Carathéodoryの拡張定理
- 直後に読む: Radonの定理(凸幾何), Hellyの定理
- 発展: 線形計画法, 組合せ幾何学
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
