Let $P_1, \dots, P_{d+1}$ be $d$-dimensional point sets such that the convex hull of each $P_i$ contains the origin. We call the sets $P_i$ color classes, and we think of the points in $P_i$ as having color $i$. A colorful choice is a set with at most one point of each color. The colorful Carathéodory theorem guarantees the existence of a colorful choice whose convex hull contains the origin. So far, the computational complexity of finding such a colorful choice is unknown.

We consider a new notion of approximation that is motivated through the applications of the colorful Carathéodory theorem in the literature: an $m$-colorful choice is a set that contains at most $m$ points from each color class. We show that for any fixed $ɛ > 0$, an $(ɛ d)$-colorful choice containing the origin in its convex hull can be found in polynomial time.

Joint work with Wolfgang Mulzer.