First Applications of Helly's Theorem

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 Rn 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 a circle circumscribing an equilateral triangle of side length 1. Indeed, Let AB be the longest side of ΔABC, implying that ∠C is the largest. It then follows that the circumcircle of an equilateral ΔABC', where C' is on the same side of AB as C, contains C is well.

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 Fk, k = 1, 2, ..., be a sequence of closed convex 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 Fk's is nonempty. Assume without loss of generality that F1 is compact. Let Gs = ∩k ≤ sFk. Then each G is compact and they all form a decreasing sequence of sets, each finite part of which has a nonempty intersection. Since F1 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

  1. Without there being a compact set, the theorem fails: let Fk = {(x, y): x ≥ k}. Being a nested family, any intersection of a finite number of sets is nonempty, whereas the whole intersection is.

  2. Without all sets being closed, the theorem fails: let Fk be open punctured (i.e., with the center removed) disks of radius 1/k centered at the origin. The disks have an empty intersection.

References

  1. H. Rademacher and O. Toeplitz, The Enjoyment of Mathematics, Dover Publications, 1990.
  2. A. Soifer, Geometric Etudes in Combinatorial Mathematics, Springer, 2010 (2nd, expanded edition)
  3. Yaglom, I. M.and V. G. Boltyanski, Convex Figures, Holt, Rinehart and Winstion, 1961

Convex Sets

|Contact| |Front page| |Contents| |Geometry|

Copyright © 1996-2018 Alexander Bogomolny

71470961