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,[1] but not published by him until 1923, by which time alternative proofs by Radon (1921) and König (1922) had already appeared.

Let X1, ..., Xn be a finite collection of convex subsets of

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).

Now we apply Radon's theorem to the set A = {x1, ..., xn}, which furnishes us with disjoint subsets A1, A2 of A such that the convex hull of A1 intersects the convex hull of A2.

Suppose that p is a point in the intersection of these two convex hulls.

Inductive Step: Suppose n > d + 2 and that the statement is true for n−1.

The argument above shows that any subcollection of d + 2 sets will have nonempty intersection.

In this new collection, every subcollection of d + 1 sets will have nonempty intersection.

The inductive hypothesis therefore applies, and shows that this new collection has nonempty intersection.