Home > Affine Geometry, Geometry, Higher Algebra > Caratheodory’s Theorem on Convex Hulls

Caratheodory’s Theorem on Convex Hulls


Caratheodory’s theorem states that if a point {x \in \Bbb{R}^d} is in the convex hull of {\Omega \subset \Bbb{R}^d}, then there is a subset {P \subset \Omega} consisting in at most {d+1} elements such that {x} lies in the convex hull of {P}.

Proof: Take {x} in the convex hull of {\Omega}. Then {x} is a convex combination of a finite number of points in {\Omega}, i.e. there exist {x_1,..,x_k \in \Omega} and {a_1,..,a_k \in [0,1]} such that {a_1+..+a_k=1} and

\displaystyle x=\sum_{i=1}^k a_ix_i.

If {i \leq d+1} then there is nothing to prove. Suppose that {k>d+1}. Then the points {x_2-x_1,..,x_k-x_1} are linearly dependent (more than {d} points in {\Bbb{R}^d} are always linearly dependent), i.e. there exist {\lambda_2,..,\lambda_k \in \Bbb{R}}, not all zero, such that

\displaystyle \sum_{i=2}^k \lambda_i(x_i-x_1)=0.

Define {\lambda_1=-\sum_{j=2}^k \lambda_j}, and note that we have

\displaystyle \sum_{i=1}^k \lambda_i x_i=0

and

\displaystyle \sum_{i=1}^k \lambda_i=0.

Since not all {\lambda_i} are zero, we can assume without losing generality that there exists a {\lambda_j>0}. Then we have for any {\alpha \in \Bbb{R}}

\displaystyle x=\sum_{i=1}^k a_i x_i-\alpha\sum_{i=1}^k \lambda_i x_i=\sum_{i=1}^k(a_i-\alpha \lambda_i)x_i.

Pick {\alpha=\displaystyle \min\{ \frac{a_j}{\lambda_j} : \lambda_j >0\}}. Then all the coefficients {a_i-\alpha \lambda_i} are positive and one of them is zero. Moreover, their sum is

\displaystyle \sum_{i=1}^k (a_i-\alpha \lambda_i)=\sum_{i=1}^k a_i=1.

Therefore we have reduced {x} to a convex combination of {k} elements of {\Omega}. We can repeat the procedure as long as {k>d+1}.

Advertisements
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: