TOPICS
Search

Colorful Carathéodory Theorem


The colorful Carathéodory theorem states that, if each of d+1 sets F_i subset= R^d has a given point in its convex hull, there are points f_i in F_i, 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 F_1,...,F_N subset R^d have |F_i|=O(d) and contain the origin in each convex hull, with a corresponding convex combination supplied for each class. If

 N>=6(d+1)dln[6(d+1)^2],

reduce each class to an origin-containing subset of at most d+1 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 1-exp[-N/(3(d+1))]. The reductions and sampling use O(Nd^4) arithmetic operations. This is a Monte Carlo guarantee, with O denoting big-O notation; it is not a deterministic algorithm for just d+1 classes. The random-choice argument builds on Soberón (2018).


See also

Caratheodory's Fundamental Theorem, Convex Hull, Tverberg's Theorem

Explore with Wolfram|Alpha

References

Bárány, I. "A Generalization of Carathéodory's Theorem." Disc. Math. 40, 141-152, 1982. https://doi.org/10.1016/0012-365X(82)90115-7.Dutta, K. and Pisula, K. "Near-Optimal Centerpoints in Polynomial Time in the Ambient Dimension." 18 Nov 2026. https://arxiv.org/abs/2611.24780v1.Soberón, P. "Robust Tverberg and Colourful Carathéodory Results via Random Choice." Combin. Probab. Comput. 27, 427-440, 2018. https://doi.org/10.1017/S0963548317000591.

Cite this as:

Weisstein, Eric W. "Colorful Carathéodory Theorem." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ColorfulCaratheodoryTheorem.html

Subject classifications