Colorful Carathéodory theorem

Remarks

Proof idea: by Carathéodory's theorem one may assume each $C_i$ is finite. Among all choices of $c_1 \in C_1, \dots, c_{d+1} \in C_{d+1}$, pick one for which the distance from $x$ to $\operatorname{conv}\set{c_1, \dots, c_{d+1}}$ is smallest. If this distance were positive, the nearest point $y$ would lie in the hull of at most $d$ of the $c_j$, so some $c_i$ could be dropped. The hyperplane through $y$ perpendicular to $x - y$ has all the $c_j$ on one side. Since $x \in \operatorname{conv}(C_i)$, some point of $C_i$ lies strictly on the side of $x$. Replacing $c_i$ by that point brings the hull closer to $x$, a contradiction.

When all the $C_i$ are the same set $C$, the theorem is Carathéodory's theorem for $C$.

Example: in the plane, let $C_1$, $C_2$, $C_3$ be red, green and blue point sets, each with the origin in its convex hull. Then some triangle with one red, one green and one blue vertex contains the origin.

Going deeper

For a student

The theorem is due to Imre Bárány. It is the key tool in Sarkaria's proof of Tverberg's theorem, and Bárány used it to prove the first selection lemma on simplices that contain a common point. It also has a colourful counterpart for Helly's theorem.