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.
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.
post by Shen-Fu Tsai