カラテオドリの定理 (凸包)

ファイル:Caratheodorys theorem example.svg

R² 内の正方形に対するカラテオドリの定理の描画例

数学の凸幾何学の分野におけるカラテオドリの定理（カラテオドリのていり、英: Carathéodory's theorem）とは、R^d 内の点 x がある集合 P の凸包に属するなら、d + 1 個あるいはそれ以下の個数の点からなる P の部分集合 P′ で、x がその凸包に属するようなものが存在する。また同値であるが、[math]r \leq d[/math] に対し、x は P 内の頂点の r-単体に属する。1911年に、P がコンパクトである場合の証明を与えたコンスタンティン・カラテオドリの名にちなむ。1914年には、エルンスト・スタイニッツがその定理を R^d 内の任意の集合 P に対して拡張した。

例えば、R² の部分集合である P = {(0,0), (0,1), (1,0), (1,1)} を考える。この集合の凸包は正方形である。今、P の凸包に属する点 x = (1/4, 1/4) を考える。このとき、凸包が三角形であるような集合 {(0,0),(0,1),(1,0)} = P′ を構成すると、x はその中に属し、|P′| = 3 であるために定理が成立する一例となる。2次元の場合は、この例のように P 内の任意の点を囲む三角形を P の点から構成することが出来るので、カラテオドリの定理を図として可視化する試みは有用となる。

証明

x を P の凸包に属する点とする。このとき x は P 内の有限個の点の凸結合である。すなわち

[math]\mathbf{x}=\sum_{j=1}^k \lambda_j \mathbf{x}_j[/math]

と書ける。但し x_j はすべて P に属し、λ_j はすべて非負であり、[math]\sum_{j=1}^k\lambda_j=1[/math] である。

k > d + 1 を仮定する（そうでない場合は証明する必要がない）。このとき、点 x₂ − x₁, ..., x_k − x₁ は線型従属であるので、ゼロでないものがある実スカラー μ₂, ..., μ_k に対して

[math]\sum_{j=2}^k \mu_j (\mathbf{x}_j-\mathbf{x}_1)=\mathbf{0} [/math]

が成り立つ。μ₁ が

[math]\mu_1:=-\sum_{j=2}^k \mu_j[/math]

のように定義されるなら、

[math]\sum_{j=1}^k \mu_j \mathbf{x}_j=\mathbf{0}[/math]

[math]\sum_{j=1}^k \mu_j=0[/math]

となり、この μ_j のすべてがゼロになることはない。したがって、少なくとも一つ μ_j > 0 となるものがある、このとき、任意の実数 α に対して

[math]\mathbf{x} = \sum_{j=1}^k \lambda_j \mathbf{x}_j-\alpha\sum_{j=1}^k \mu_j \mathbf{x}_j = \sum_{j=1}^k (\lambda_j-\alpha\mu_j) \mathbf{x}_j[/math]

が成り立つ。特に、等号は α が次のように定義されたときに成り立つ。

[math] \alpha:=\min_{1\leq j \leq k} \left\{ \tfrac{\lambda_j}{\mu_j}:\mu_j\gt 0\right\}=\tfrac{\lambda_i}{\mu_i}.[/math]

ここで α>0 であり、1 と k の間のすべての j に対して

[math]\lambda_j-\alpha\mu_j \geq 0 [/math]

であることに注意されたい。特に α の定義から λ_i − αμ_i = 0 である。したがって

[math]\mathbf{x} = \sum_{j=1}^k (\lambda_j-\alpha\mu_j) \mathbf{x}_j[/math]

が成り立つ。但しすべての [math]\lambda_j - \alpha \mu_j[/math] は非負で、それらの和は 1 で、[math]\lambda_i-\alpha\mu_i=0[/math] である。言い換えると、x は高々 k-1 個の P の点の凸結合として表現される。この過程を x が高々 d + 1 個の P の点の凸結合として表現されるまで繰り返せばよい。

またこの他の証明ではヘリーの定理が用いられる。

関連項目

• シャプレー＝フォークマンの補題
• ヘリーの定理
• クレイン＝ミルマンの定理
• ショケー理論

参考文献

• Carathéodory, C. (1911), “Über den Variabilitätsbereich der Fourierschen Konstanten von positiven harmonischen Funktionen”, Rendiconti del Circolo Matematico di Palermo 32: 193–217, doi:10.1007/BF03014795 .
• Danzer, L.; Grünbaum, B.; Klee, V. (1963), “Helly's theorem and its relatives”, Convexity, Proc. Symp. Pure Math., 7, American Mathematical Society, pp. 101–179 .
• Eckhoff, J. (1993), “Helly, Radon, and Carathéodory type theorems”, Handbook of Convex Geometry, A, B, Amsterdam: North-Holland, pp. 389–448 .
• Steinitz, Ernst (1913), “Bedingt konvergente Reihen und konvexe Systeme”, J. Reine Angew. Math. 143 (143): 128–175, doi:10.1515/crll.1913.143.128. 

外部リンク

• 凸包に関する定理の簡単な内容（PlanetMath）