Added to Favorites

Related Searches

Definitions

Nearby Words

- See also Carathéodory's theorem for other meanings

For example, consider a set P = {(0,0), (0,1), (1,0), (1,1)} which is a subset of R^{2}. 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.

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_{2} − x_{1}, ..., x_{k} − x_{1} are linearly dependent, so there are real scalars μ_{2}, ..., μ_{k}, not all zero, such that

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

If μ_{1} 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\{\; tfrac\{lambda\_j\}\{mu\_j\}:mu\_j>0right\}=tfrac\{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.

- 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.

- Concise statement of theorem in terms of convex hulls (at PlanetMath)

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Friday September 12, 2008 at 06:52:03 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Friday September 12, 2008 at 06:52:03 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2014 Dictionary.com, LLC. All rights reserved.