Editing Carathéodory's theorem (convex hull) (section)

=== {{Anchor|colorful}}Colorful Carathéodory theorem ===
Let ''X''<sub>1</sub>, ..., ''X''<sub>''d''+1</sub> be sets in '''R'''<sup>''d''</sup> and let ''x'' be a point contained in the intersection of the convex hulls of all these ''d''+1 sets.

Then there is a set ''T'' = {''x''<sub>1</sub>, ..., ''x''<sub>''d''+1</sub>}, where {{math|''x''<sub>1</sub> ∈ ''X''<sub>1</sub>, ..., ''x''<sub>''d''+1</sub> ∈ ''X''<sub>''d''+1</sub>}}, such that the convex hull of ''T'' contains the point ''x''.<ref name=":0">{{Cite journal|date=1982-01-01|title=A generalization of carathéodory's theorem|journal=Discrete Mathematics|language=en|volume=40|issue=2–3|pages=141–152|doi=10.1016/0012-365X(82)90115-7|issn=0012-365X|last1=Bárány|first1=Imre|doi-access=free}}</ref>

By viewing the sets ''X''<sub>1</sub>, ..., ''X''<sub>''d''+1</sub>  as different colors, the set ''T'' is made by points of all colors, hence the "colorful" in the theorem's name.<ref>{{Cite journal|last1=Montejano|first1=Luis|last2=Fabila|first2=Ruy|last3=Bracho|first3=Javier|last4=Bárány|first4=Imre|last5=Arocha|first5=Jorge L.|date=2009-09-01|title=Very Colorful Theorems|journal=Discrete & Computational Geometry|language=en|volume=42|issue=2|pages=142–154|doi=10.1007/s00454-009-9180-4|issn=1432-0444|doi-access=free}}</ref> The set ''T'' is also called a ''rainbow simplex'', since it is a ''d''-dimensional [[simplex]] in which each corner has a different color.<ref name="Mustafa 1300–1305">{{Cite journal|last1=Mustafa|first1=Nabil H.|last2=Ray|first2=Saurabh|date=2016-04-06|title=An optimal generalization of the Colorful Carathéodory theorem|journal=Discrete Mathematics|language=en|volume=339|issue=4|pages=1300–1305|doi=10.1016/j.disc.2015.11.019|issn=0012-365X|doi-access=free}}</ref>

This theorem has a variant in which the convex hull is replaced by the [[conical hull]].<ref name=":0" />{{Rp|Thm.2.2}}  Let ''X''<sub>1</sub>, ..., ''X''<sub>''d''</sub> be sets in '''R'''<sup>d</sup> and let ''x'' be a point contained in the intersection of the ''conical hulls'' of all these ''d'' sets. Then there is a set ''T'' = {''x''<sub>1</sub>, ..., ''x''<sub>''d''</sub>}, where {{math|''x''<sub>1</sub> ∈ ''X''<sub>1</sub>, ..., ''x''<sub>''d''</sub> ∈ ''X''<sub>''d''</sub>}}, such that the ''conical hull'' of ''T'' contains the point ''x''.<ref name=":0" />

Mustafa and Ray extended this colorful theorem from points to convex bodies.<ref name="Mustafa 1300–1305"/>

The computational problem of finding the colorful set lies in the intersection of the complexity classes [[PPAD (complexity)|PPAD]] and [[PLS (complexity)|PLS]].<ref>{{Citation |last1=Meunier |first1=Frédéric |title=The Rainbow at the End of the Line ? A PPAD Formulation of the Colorful Carathéodory Theorem with Applications |date=2017-01-01 |work=Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) |pages=1342–1351 |series=Proceedings |publisher=Society for Industrial and Applied Mathematics |doi=10.1137/1.9781611974782.87 |last2=Mulzer |first2=Wolfgang |last3=Sarrabezolles |first3=Pauline |last4=Stein |first4=Yannik|isbn=978-1-61197-478-2 |s2cid=5784949 |doi-access=free |arxiv=1608.01921 }}</ref>