Carathéodory's theorem (convex hull)

:"See also Carathéodory's theorem for other meanings"In convex geometry Carathéodory's theorem states that if a point "x" of R^"d" lies in the convex hull of a set "P", there is a subset "P"′ of "P" consisting of "d"+1 or fewer points such that "x" lies in the convex hull of "P"′. Equivalently, "x" lies in a "r"-simplex with vertices in "P", where $r\; leq\; d$. The result is named for Constantin Carathéodory, who proved the theorem in 1911 for the case when "P" is compact. In 1914 Steinitz expanded Carathéodory's theorem for any sets "P" in R^d.

For example, consider a set "P" = {(0,0), (0,1), (1,0), (1,1)} which is a subset of R². The convex hull of this set is a square. Consider now a point "x" = (1/4, 1/4), which is in the convex hull of "P". We can then construct a set {(0,0),(0,1),(1,0)} = "P" ′, the convex hull of which is a triangle and encloses "p", and thus the theorem works for this instance, since |"P"′| = 3. It may help to visualise Carathéodory's theorem in 2 dimensions, as saying that we can construct a triangle consisting of points from "P" that encloses any point in "P".

Proof

Let "x" be a point in the convex hull of "P". Then, "x" is a convex combination of a finite number of points in "P" :

:$mathbf\{x\}=sum\_\{j=1\}^k\; lambda\_j\; mathbf\{x\}\_j$

where every "x"_j is in "P", every "λ"_j is positive, and $sum\_\{j=1\}^klambda\_j=1$.

Suppose "k" > "d" + 1 (otherwise, there is nothing to prove). Then, the points "x"₂ − "x"₁, ..., "x"_"k" − "x"₁ are linearly dependent, so there are real scalars "μ"₂, ..., "μ"_"k", not all zero, such that

:$sum\_\{j=2\}^k\; mu\_j\; (mathbf\{x\}\_j-mathbf\{x\}\_1)=mathbf\{0\}.$

If "μ"₁ is defined as

:$mu\_1:=-sum\_\{j=2\}^k\; mu\_j$

then

:$sum\_\{j=1\}^k\; mu\_j\; mathbf\{x\}\_j=mathbf\{0\}$:$sum\_\{j=1\}^k\; mu\_j=0$

and not all of the μ_"j" are equal to zero. Therefore, at least one "μ"_j>0. Then,

:$mathbf\{x\}\; =\; sum\_\{j=1\}^k\; lambda\_j\; mathbf\{x\}\_j-alphasum\_\{j=1\}^k\; mu\_j\; mathbf\{x\}\_j\; =\; sum\_\{j=1\}^k\; (lambda\_j-alphamu\_j)\; mathbf\{x\}\_j$

for any real "α". In particular, the equality will hold if "α" is defined as

:$alpha:=min\_\{1leq\; j\; leq\; k\}\; left\{\; frac\{lambda\_j\}\{mu\_j\}:mu\_j>0\; ight\}=\; frac\{lambda\_i\}\{mu\_i\}.$

Note that "α">0, and for every "j" between 1 and "k",:$lambda\_j-alphamu\_j\; geq\; 0.$

In particular, "λ"_i − "αμ"_"i" = 0 by definition of "α". Therefore,

:$mathbf\{x\}\; =\; sum\_\{j=1\}^k\; (lambda\_j-alphamu\_j)\; mathbf\{x\}\_j$

where every $lambda\_j\; -\; alpha\; mu\_j$ is nonnegative, their sum is one , and furthermore, $lambda\_i-alphamu\_i=0$. In other words, "x" is represented as a convex combination of at most "k"-1 points of "P". This process can be repeated until "x" is represented as a convex combination of at most "d" + 1 points in "P".

Q.E.D.

References

*C. Caratheodory, Über den Variabilitätsbereich der Fourierschen Konstanten von positiven harmonischen Funktionen, Rend. Circ. Mat. Palermo, Vol. 32 (1911), 193-217.

* E. Steinitz, Bedingt konvergente Reihen und konvexe Systeme, I-IV, J. Reine Angew. Math. Vol. 143 (1913), 128-175.

External links

* [http://planetmath.org/encyclopedia/CaratheodorysTheorem2.html Concise statement of theorem] in terms of convex hulls (at PlanetMath)