Carathéodory's theorem
/ ka-ra-tay-OH-do-ree /
If a point sits inside the convex hull of a huge cloud of points, you might fear you need the whole cloud to express it. Carathéodory's theorem reassures you: in n dimensions you never need more than n + 1 of the points. Any point in the hull is already a weighted average of at most n + 1 of the originals — a tiny committee always suffices to vouch for it. In the plane, three points; in space, four; the dimension plus one is all you ever require.
Precisely, if a point x lies in the convex hull of a set S in R^n, then x lies in the convex hull of some subset of S with at most n + 1 points. Equivalently, x = sum t_i v_i is a convex combination using at most n + 1 of the v_i in S. The proof is a reduction argument: if x is written as a convex combination of more than n + 1 points, those points are affinely dependent, so there is a nonzero relation sum c_i v_i = 0 with sum c_i = 0; adding a suitable multiple of this relation to the weights drives one weight to zero while keeping the rest nonnegative and summing to 1 — you have re-expressed x with one fewer point. Repeat until only n + 1 remain.
Carathéodory's theorem is why the convex hull of a finite set is a polytope with finitely many vertices, and it is the third member of the Helly-Radon-Caratheodory trio, all provable from the same affine-dependence idea. It underpins algorithms (you can always sparsify a representation to n + 1 atoms), the Shapley-Folkman lemma in economics (approximate convexity of sums of non-convex sets), and the theory of extreme points. Two honest caveats. First, n + 1 is the sharp bound, attained by points in general position (the center of a simplex genuinely needs all n + 1 vertices), so you cannot in general do with fewer. Second, the theorem gives existence of a small representing subset, not uniqueness or a procedure to find the best one — there can be many valid (n + 1)-point committees for the same x.
In the plane (n = 2) take the unit square's four corners and the center point (1/2, 1/2). The center is a convex combination of all four corners with weights 1/4 each — but Carathéodory promises three suffice. And indeed the center sits inside triangle formed by, say, (0,0), (1,0), (0,1) extended; more cleanly, it is the midpoint of the diagonal, a convex combination of just two corners (0,0) and (1,1). At most n + 1 = 3 points always work, often fewer.
The square's center needs at most 3 corners (here just 2, the diagonal midpoint).
The bound n + 1 is sharp but is an upper bound — many points need fewer, and the representing subset is not unique. There is also a 'colorful Caratheodory' refinement (Barany): if x lies in n + 1 colored hulls, a rainbow subset of one point per color already contains x.