Helly's theorem

Helly's theorem is a basic result in discrete geometry on the intersection of convex sets. It was discovered by Eduard Helly in 1913, but not published by him until 1923, by which time alternative proofs by Radon (1921) and König (1922) had already appeared. Helly's theorem gave rise to the notion of a Helly family.

Let $X 1, ..., X n$ be a finite collection of convex subsets of $R d$ , with $n > d$ . If the intersection of every $d + 1$ of these sets is nonempty, then the whole collection has a nonempty intersection; that is,

For infinite collections one has to assume compactness:

Let ${X α}$ be a collection of compact convex subsets of $R d$ , such that every subcollection of cardinality at most $d + 1$ has nonempty intersection, then the whole collection has nonempty intersection.

We prove the finite version, using Radon's theorem as in the proof by Radon (1921). The infinite version then follows by the finite intersection property characterization of compactness: a collection of closed subsets of a compact space has a non-empty intersection if and only if every finite subcollection has a non-empty intersection (once you fix a single set, the intersection of all others with it are closed subsets of a fixed compact space).

The proof is by induction:

Base case: Let $n = d + 2$ . By our assumptions, for every $j = 1, ..., n$ there is a point $x j$ that is in the common intersection of all $X i$ with the possible exception of $X j$ . Now we apply Radon's theorem to the set $A = {x 1, ..., x n},$ which furnishes us with disjoint subsets $A 1, A 2$ of $A$ such that the convex hull of $A 1$ intersects the convex hull of $A 2$ . Suppose that $p$ is a point in the intersection of these two convex hulls. We claim that

...
Wikipedia