Carathéodory's theorem

Statement

Let $P$ be a subset of $\mathbb{R}^d$, and let $x$ be a point of its convex hull $\operatorname{conv}(P)$. Then there are at most $d + 1$ points $p_1, \dots, p_k$ of $P$, with $k \leq d + 1$, such that $x \in \operatorname{conv}\{p_1, \dots, p_k\}$. Equivalently, $x$ is a convex combination of at most $d + 1$ points of $P$.

Remarks

Thus $\operatorname{conv}(P)$ is the union of the simplices with vertices in $P$, of dimension at most $d$. Mathlib states this form as convexHull_eq_union. The bound $d + 1$ is the best possible in general. Let $P$ be the three vertices of a triangle in $\mathbb{R}^2$. A point inside the triangle is not in the hull of two points of $P$. The proof only uses the order and the field operations of $\mathbb{R}$. So it works over each ordered field.

History

Carathéodory proved the theorem in 1911 for compact sets $P$. Steinitz extended it to arbitrary sets in 1914.

Explanations

L1 human

In the plane, a point in the convex hull of many points is always inside a triangle with corners from those points. You never need more than three corners. In space, four corners, the vertices of a tetrahedron, are always enough.