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