Helly's theorem is a result from combinatorial geometry that explains how convex sets may intersect each other. The theorem is often given in greater generality, though for our considerations, we will mainly apply it to the plane.
We begin with a definition of a convex set. A set is convex, if for every pair of points and in , the line segment lies within . Note that the empty set is trivially a convex set, since there are no points within it.
Lemma: The intersection of two convex sets is convex.
Proof: Consider two convex sets and . Let . Take any 2 points and in . These points lie in (and in ). By definition of convex, the line segment lies in (and in ). Hence, lies in their intersection, which is . Thus, is convex. .
For those who are familiar with convex functions, we say that a function is convex if the graph and the region above it, is a convex set. This is one way to remember the difference between a convex and concave function.
Helly's Theorem: Suppose is a collection of convex sets in , with . If the intersection of every of these sets is non-empty, then the entire collection has a non-empty intersection.
This is a very surprising result. Knowledge of a local property (every of the sets intersect) implies a global property (all of these sets must intersect), which is extremely rare.
We will prove the theorem in the case (i.e., the plane). The general case proceeds in a similar manner and the reader is invited to flesh out the details. In the Worked Examples, we give a different way of approaching , though that method doesn't easily extend to higher dimensions.
We first prove a Lemma, which is Helly's Theorem for .
Lemma: Given 4 convex subsets of the plane, if every 3 of them have a non-empty intersection, then all 4 of them have a non-empty intersection.
Proof: Let the subsets be . Define to be a common point of the three sets which do not include . Now, consider the configuration of these 4 pointa.
If the convex hull of these 4 points is a triangle, WLOG let be in the interior. Then since is within , hence is within the triangle given by and hence is within . So is in all four sets.
If the convex hull of these 4 points is a convex quadrilateral, WLOG let the points be ordered as . Now consider the diagonals and . Since it is a convex quadrilateral, they intersect at a point . Then, since , hence is in sets and . Similarly, since , hence is in sets and . Thus, is in all four sets. .
We are now ready to prove Helly's Theorem in the plane.
Proof: We proceed by induction, in a slightly tricky manner. The base case is trivially true. The base case is the above Lemma.
For the induction step, suppose the theorem holds for some . Given any set of subsets , consider the set of subsets . From the intersection property, we know that is a convex set for all .
Now, consider the intersection of any 3 sets. We have
which is nonempty by the Lemma. Applying the induction hypothesis to the sets , we conclude that the intersection of all sets is non-empty. But since , it follows that the interesction of is also non-empty.
The requirement of a finite collection of subsets is necessary. For example, on the number line, the collection of sets satisfies the property that any 2 of them have a non-empty intersection, but the intersection of all of these sets is empty. However, for an infinite collection of compact, convex subsets, Helly's Theorem still holds.
Prove Helly's Theorem for , i.e., the case of the line.
Solution: The only convex sets on the line are line segments. To each of these sets, we will colour the left most point red, and the right most point blue. Then, the condition of intersection tells us that the red points must all occur to the left of the blue point.
We now consider the right most red point, and the left most blue point. If these 2 points are the same, then this point must lie in all of our sets. If these 2 points are distinct, then the line segment connecting these 2 points must lie in all of our sets. Hence we are done.
Note: As you can see, this is a straightforward argument, especially when compared with the above proof of Helly's Theorem. However, it doesn't extend to higher dimensions.
Find a collection of 3 sets in the plane ( ), such that every 2 of them intersect, but all 3 of them do not intersect.
Solution: Let be a non-degenerate triangle. Let the sets be the line segments . Clearly, any 2 of them intersect (at a vertex), and the 3 of them do not intersect.
Note: This shows that the requirement that every sets have a non-empty intersection is strict. Do you see how to generalize this counter example to all ?
Let be a finite set of points in the plane, such that the distance between any 2 points is smaller than 1. Show that there exists a disk of radius 1 which covers all of these points.
Solution: Let be disks of radius 1 with center . Then, every 3 of these disks and have a non-empty intersection, since we know that the point lies in . Hence, by Helly's Theorem, there is a point which lies in , which means that the distance between and is less than 1. Hence, the disk of radius 1 with center covers all of these points.
Note: Can you improve on this, and use a disk of smaller radius?