First Applications of Helly's Theorem

For the reference's sake, Helly's theorem tells us that, given a finite family C of convex sets in Rⁿ such that, for k ≤ n + 1, any k members of C have a nonempty intersection, then the intersection of all members of C is nonempty.

Let's have a few simple applications of the theorem.

Statement 1

Given s (s > 0) points in the plane such that every three of them are contained in a disk of radius 1. Prove that all s points are contained in a disk of radius 1.

Proof

Consider the set C of unit disks with centers at the points from a given set. Since every three of the given points are contained in a unit disk, any three disks from C have a nonempty intersection. By Helly's Theorem, all the disks have a nonempty intersection. Let q be a point from the intersection. Then q belongs to every disk from C and is, therefore, at a distance less than 1 from there centers. In other words, all the centers of the disks from C lie in a disk of radius 1 centered at q.

Statement 2 (H. Jung's Theorem)

Let M be a finite set of points in the plane, with all pairwise distance between them not exceeding 1. Then M is contained in a disk of radius 1/√3.

Observe that in the statement and the proof 1 could be replaced with an arbitrary positive constant.

Proof

Every three points A, B, C, with pairwise distances not exceeding 1, are contained in an equilateral triangle of side length 1. Indeed, Let AB be the logest side of & ΔABC, implying that ∠C is the largest. It then follows that both angles at A and B are less than 60°. Trying to construct ΔABC, we see that C falls inside the equilateral triangle ABC'.

Now, a circumradius of an equilateral with side 1 equals √3 / 3 = 1 / √3. Thus, every three points from set M are contained in a disk of radius 1 / √3. By Statement 1, the whole of the set M lies in a disk of that radius.

For the infinite families of sets Helly's theorem also holds, with an extra requirement.

Statement 3

(Helly's Theorem for an Infinite Family of Sets)

Let F_k, k = 1, 2, ..., be a sequence of closed figures in the plane of which at least one is compact. Then if any three of the figures have nonempty intersection, the intersection of the whole family is nonempty.

Proof

By Helly's theorem, the intersection of a finite number of F_k's is nonempty. Assume without loss of generality that F₁ is compact. Let G_s = ∩_{k ≤ s}F_k. Then each G is compact and they all form a decreasing sequence of sets, each finite part of which has a nonempty intersection. Since F₁ is compact it has the Finite Intersection Property so that the intersection of all G's is nonempty but then the same holds for the intersection of all F's because the two intersections coincide.

Remark

Without there being a compact set, the theorem fails: let F_k = {(x, y): x ≥ k}. Being a nested family, any intersection of a finite number of sets is nonempty, whereas the whole intersection is.
Without all sets being closed, the theorem fails: let F_k be open disks of radius 1/k centered at the origin. The disks have an empty intersection.

References

A. Soifer, Geometric Etudes in Combinatorial Mathematics, Springer, 2010 (2nd, expanded edition)
Yaglom, I. M.and V. G. Boltyanski, Convex Figures, Holt, Rinehart and Winstion, 1961

Convex Sets

41173509