The colorful Carathéodory theorem states that, if each of sets
has a given point in its convex
hull, there are points
,
one from each set, such that the chosen points still have that point in their convex hull (Bárány 1982). Taking all sets
equal recovers Carathéodory's
fundamental theorem.
Dutta and Pisula (2026) gave a randomized algorithm for a regime with more color classes. Let have
and contain the origin
in each convex hull, with a corresponding convex
combination supplied for each class. If
reduce each class to an origin-containing subset of at most points and choose one point independently and uniformly
from each reduced class. The chosen set contains the origin
in its convex hull with probability
at least
. The reductions and sampling use
arithmetic operations. This is a Monte Carlo guarantee, with
denoting big-O notation;
it is not a deterministic algorithm for just
classes. The random-choice argument builds on Soberón
(2018).