Caratheodory's theorem

December 22, 2017

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 xx of RdRd lies in the convex hull of a set P={p1,…,pn}P={p1,…,pn}, then xx can be written as the convex combination of at most d+1d+1 points in PP.

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

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

post by Shen-Fu Tsai