1. 高校数学の美しい物語
  2. 凸包に関するカラテオドリの定理とその証明

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

更新日時 2021/03/07

カラテオドリの定理:

AARn\mathbb{R}^n の部分集合 SS の凸包に含まれているとき,SS から n+1n+1 個の点をうまく選んでくれば,その n+1n+1 個の点の凸包に AA が含まれるようにできる。

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

目次
  • 定理に登場する用語

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

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

定理に登場する用語

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

集合の凸包

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

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

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

カラテオドリの定理(n=2n=2 ):

AA が平面の部分集合 SS の凸包に含まれているとき,SS から 33 個の点をうまく選んでくれば,その 33 個の点を頂点とする三角形に AA が含まれるようにできる。

カラテオドリの定理

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

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

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

A(aundefined)A(\overrightarrow{a})SS の凸包に含まれる

AASS の有限個の点 Pi(pundefinedi)(i=1,,N)P_i(\overrightarrow{p}_i)\:(i=1,\cdots, N) の凸結合で書ける

ことは認めます。

証明

AASS の凸包に含まれるので,SS の有限個の点 Pi(pundefinedi)(i=1,,N)P_i(\overrightarrow{p}_i)\:(i=1,\cdots, N) を用いて aundefined=i=1Nλipiundefined\overrightarrow{a}=\displaystyle\sum_{i=1}^N\lambda_i\overrightarrow{p_i} と書ける(*)。

ただし,λi0,i=1Nλi=1\lambda_i\geq 0,\displaystyle\sum_{i=1}^N\lambda_i=1

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

さて,Nn+2N\geq n+2 なら,N1N-1 本のベクトル piundefinedp1undefined(i=2,N)\overrightarrow{p_i}-\overrightarrow{p_1}\:(i=2,\cdots N) は一次従属なので,

i=2Nμi(piundefinedp1undefined)=0undefined\displaystyle\sum_{i=2}^N\mu_i(\overrightarrow{p_i}-\overrightarrow{p_1})=\overrightarrow{0} と表現できる。ただし,μk0\mu_k\neq 0 となる kk が存在する。

これを使って AA を表す式(*)をズラす:

aundefined=i=1Nλipiundefined+ti=2Nμi(piundefinedp1undefined)=i=1Nλipiundefined\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}

ただし,λ1=λ1ti=2Nμi\lambda'_1=\lambda_1-t\displaystyle\sum_{i=2}^N\mu_i

λi=λi+tμi(i=2,,N)\lambda'_i=\lambda_i+t\mu_i\:(i=2,\cdots, N)

ここで,i=1Nλi=i=1Nλi=1\displaystyle\sum_{i=1}^N\lambda'_i=\sum_{i=1}^N\lambda_i=1 に注意する。

tt を適切に選んでやると λi\lambda'_i のいくつかは 00 で残りは全て正になるようにできる(→注)。つまり,aundefined\overrightarrow{a}N1N-1 個以下の SS の点の凸結合で表せたことになる。

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

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

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

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

人気記事
  1. 高校数学の美しい物語
  2. 凸包に関するカラテオドリの定理とその証明