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

数学のの分野におけるカラテオドリの定理（カラテオドリのていり、）とは、R"d" 内の点 "x" がある集合 "P" の凸包に属するなら、"d" + 1 個あるいはそれ以下の個数の点からなる "P" の部分集合 "P"′ で、"x" がその凸包に属するようなものが存在する。また同値であるが、formula_1 に対し、"x" は "P" 内の頂点の "r"-単体に属する。1911年に、"P" がコンパクトである場合の証明を与えたコンスタンティン・カラテオドリの名にちなむ。1914年には、がその定理を Rd 内の任意の集合 "P" に対して拡張した。
例えば、R2 の部分集合である "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" 内の有限個の点の凸結合である。すなわち
と書ける。但し xj はすべて "P" に属し、"λ"j はすべて非負であり、formula_3 である。
"k" > "d" + 1 を仮定する（そうでない場合は証明する必要がない）。このとき、点 x2 − x1, ..., x"k" − x1 は線型従属であるので、ゼロでないものがある実スカラー "μ"2, ..., "μ""k" に対して
が成り立つ。"μ"1 が
のように定義されるなら、
となり、この μ"j" のすべてがゼロになることはない。したがって、少なくとも一つ "μ"j > 0 となるものがある、このとき、任意の実数 "α" に対して
が成り立つ。特に、等号は "α" が次のように定義されたときに成り立つ。
ここで "α">0 であり、1 と "k" の間のすべての "j" に対して
であることに注意されたい。特に "α" の定義から "λ"i − "αμ""i" = 0 である。したがって
が成り立つ。但しすべての formula_12 は非負で、それらの和は 1 で、formula_13 である。言い換えると、x は高々 "k"-1 個の "P" の点の凸結合として表現される。この過程を x が高々 "d" + 1 個の "P" の点の凸結合として表現されるまで繰り返せばよい。
またこの他の証明ではヘリーの定理が用いられる。