---
tag: X5GS407VP8
kind: statement
role: theorem
name: Colorful Carathéodory theorem
msc: [52A35]
uses: [0XPR1E85W0, 0FQSDC2EQ2, 0201Q4P2B5]
about: [0FQSDC2EQ2]
sources:
  - url: https://en.wikipedia.org/wiki/Carath%C3%A9odory%27s_theorem_(convex_hull)
---

## Statement

Let $d \ge 1$ and let $C_1, \dots, C_{d+1}$ be subsets of $\R^d$.
Let $x \in \R^d$ be a point that lies in the [[convex hull|0FQSDC2EQ2]] of each $C_i$, for $i = 1, \dots, d + 1$.
Then there are points $c_1 \in C_1, \dots, c_{d+1} \in C_{d+1}$ such that
$$x \in \operatorname{conv}\set{c_1, \dots, c_{d+1}}.$$

## Remarks

Proof idea: by [[Carathéodory's theorem|0201Q4P2B5]] 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.

## Explanations

### L1 human

Colour points with $d + 1$ colours, and suppose that the points of each colour surround a given point $x$.
Then you can pick one point of each colour so that these $d + 1$ points already surround $x$.
In the plane: three colour classes each surrounding $x$ give a rainbow triangle around $x$.

### L2 human

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.