# Caratheodory's theorem

Previous I used Caratheodory's theorem to prove Radon's theorem, now I'm going to prove the former.

Caratheodory's theorem: if a point $$x$$ of $$R^d$$ lies in the convex hull of a set $$P=\{p_1,\ldots,p_{n}\}$$, then $$x$$ can be written as the convex combination of at most $$d+1$$ points in $$P$$.

Proof:
It suffices to prove it for $$|P|=d+2$$, and then for $$|P|=d+3$$ we can reduce the convex combination of $$p_1,\ldots,p_{d+2}$$ to that of some $$d+1$$ points in $$\{p_1,\ldots,p_{d+2}\}$$ which together with $$p_{d+3}$$ can be reduced again to convex combination of some $$d+1$$ points, and so on.

Let $$P'=\{p_1,\ldots,p_{d+1}\}$$. Given $$x\in conv(P)$$, if $$x\in conv(P')$$ then we are done. If not, note that it is nevertheless the convex combination of $$p_{d+2}$$ and $$z\in conv(P')$$. So $$x$$ belongs to segment $$zp_{d+2}$$. Consider point y, one of the intersections of $$zp_{d+2}$$ and boundary of $$conv(P')$$. Point $$x$$ must lie between $$y$$ and $$p_{d+2}$$, so it is the convex combination of the two as well. As $$y$$ is at the boundary of $$conv(P')$$, it could be represented as convex combination of $$P'$$ with at least one zero coefficient, i.e. at most $$d$$ points with positive coefficient. So $$x$$ can be written as convex combination of $$P$$ with at most $$d+1$$ positive coefficients.
Q.E.D.