|
|
|
|
|
Carathodory's Theorem (Convex Hull)In mathematics Carathodory's theorem on convex sets states that if a point x of Rd lies in the convex hull of a set P, there is a subset P′ of P consisting of no more than d+1 points such that x lies in the convex hull of P′. . In other words, x lies in a d-simplex with vertices in P. The result is named for Constantin Carathodory. For example, consider a set P, {(0,0), (0,1), (1,0), (1,1)} which is a subset of R2. 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 Carathodory'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 points in P: -
where every xj is in P, every λj is nonnegative, and . Suppose k>d+1 (otherwise, there is nothing to prove). Then, the points x2-x1, ..., xk-x1 are linearly dependent, so there are real scalars μ2, ..., μk, not all zero, such that -
If μ1 is defined as -
then -
-
and not all of the μj are equal to zero. Therefore, at least one μj>0. Then, -
for any real α. In particular, the equality will hold if α is defined as -
Note that α>0, and for every j between 1 and k, -
In particular, λi-αμi=0 by definition of α. Therefore, -
where every λj-αμj is nonnegative, their sum is one , and furthermore, . 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. External links
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|