2015/08/18

凸包に関するカラテオドリの定理とその証明

分野: 空間図形  レベル: 大学数学

カラテオドリの定理:
$A$ が $\mathbb{R}^n$ の部分集合 $S$ の凸包に含まれているとき,$S$ から $n+1$ 個の点をうまく選んでくれば,その $n+1$ 個の点の凸包に $A$ が含まれるようにできる。

基本的な用語の解説→ $n=2$ の場合で定理の意味をつかむ→定理の証明。

定理に登場する用語

・ $\mathbb{R}^n$ は $n$ 次元ユークリッド空間です。 $n=1$ のときは数直線,$n=2$ のとき座標平面,$n=3$ のときは座標空間をイメージしてもらえればOKです。

集合の凸包
  • 集合 $S$ の凸包とは,$S$ を含む最小の凸集合(へこんでいない領域)です。 $n=2$ のときは,点のところに釘を打って輪ゴムをかけるというイメージです。
  • 測度論におけるカラテオドリの定理もあります。そのため「凸包に関する」カラテオドリと書いています。

平面におけるカラテオドリの定理

$n=2$ の場合でカラテオドリの定理の主張を確認してみます。

カラテオドリの定理($n=2$):
$A$ が平面の部分集合 $S$ の凸包に含まれているとき,$S$ から $3$ 個の点をうまく選んでくれば,その $3$ 個の点を頂点とする三角形に $A$ が含まれるようにできる。

カラテオドリの定理

例えば図において,凸包に含まれている点は必ず三つの三角形のいずれか(境界も含む)に含まれているのでカラテオドリの定理は成立しています。

二次元で凸包が多角形の場合,凸包を三角形分割すればそりゃそうだろって感じはしますね。

カラテオドリの定理の証明

$A(\overrightarrow{a})$ が $S$ の凸包に含まれる
→ $A$ が $S$ の有限個の点 $P_i(\overrightarrow{p}_i)\:(i=1,\cdots, N)$ の凸結合で書ける
ことは認めます。

証明

$A$ が $S$ の凸包に含まれるので,$S$ の有限個の点 $P_i(\overrightarrow{p}_i)\:(i=1,\cdots, N)$ を用いて $\overrightarrow{a}=\displaystyle\sum_{i=1}^N\lambda_i\overrightarrow{p_i}$ と書ける(*)。
ただし,$\lambda_i\geq 0,\displaystyle\sum_{i=1}^N\lambda_i=1$

「今のところ $A$ は $N$ 個の点の凸結合で表現されているが,もし $N\geq n+2$ なら,係数 $\lambda$ を調整することで $N-1$ 個の凸結合でも表現できる」ことを証明すればOK(一つずつ減らしていって $n+1$ 個の点の凸結合で書けることが言える)。

さて,$N\geq n+2$ なら,$N-1$ 本のベクトル $\overrightarrow{p_i}-\overrightarrow{p_1}\:(i=2,\cdots N)$ は一次従属なので,
$\displaystyle\sum_{i=2}^N\mu_i(\overrightarrow{p_i}-\overrightarrow{p_1})=\overrightarrow{0}$ と表現できる。ただし,$\mu_k\neq 0$ となる $k$ が存在する。

これを使って $A$ を表す式(*)をズラす:
$\overrightarrow{a}=\displaystyle\sum_{i=1}^N\lambda_i\overrightarrow{p_i}+t \sum_{i=2}^N\mu_i(\overrightarrow{p_i}-\overrightarrow{p_1})\\
=\displaystyle\sum_{i=1}^N\lambda’_i\overrightarrow{p_i}$
ただし,$\lambda’_1=\lambda_1-t\displaystyle\sum_{i=2}^N\mu_i$
$\lambda’_i=\lambda_i+t\mu_i\:(i=2,\cdots, N)$
ここで,$\displaystyle\sum_{i=1}^N\lambda’_i=\sum_{i=1}^N\lambda_i=1$ に注意する。

$t$ を適切に選んでやると $\lambda’_i$ のいくつかは $0$ で残りは全て正になるようにできる(→注)。つまり,$\overrightarrow{a}$ が $N-1$ 個以下の $S$ の点の凸結合で表せたことになる。

注:$\lambda_i$ たちはもともと非負であり,$\mu_k\neq 0$ となる $k$ が存在するので $t$ を $0$ から少しずつ動かしていく($\mu_k$ が正なら $t$ を減らしていく,$\mu_k$ が負なら $t$ を増やしていく)とどこかで $\lambda’_i=0$ となる $i$ が出現する。

なお,証明はWikipediaを参考にしました。

空手踊りの定理。名前のインパクトは抜群です。

Tag: 数学の定理No.1決定戦

分野: 空間図形  レベル: 大学数学