Helly's Theorem

Helly's theorem is a result from combinatorial geometry, which 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 $X$ is convex, if for every pair of points $p$ and $q$ in $X$, the line segment $\overline{pq}$ lies within $X$. 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 $X_1$ and $X_2$. Let $X = X_1 \cap X_2$. Take any 2 points $p$ and $q$ in $X$. These points lie in $X_1$ (and in $X_2$ ). By definition of convex, the line segment $\overline{pq}$ lies in $X_1$ (and in $X_2$ ). Hence, $\overline{pq}$ lies in their intersection, which is $X$. Thus, $X$ is convex. $_\square$.

For those who are familiar with convex functions, we say that a function $f(x)$ 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.

Now, we are ready to learn about Helly's Theorem.

Helly's Theorem: Suppose $X_1, X_2, \ldots, X_n$ is a collection of convex sets in $\mathbb{R} ^d$, with $n > d$. If the intersection of every $d+1$ 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 $d+1$ 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 $d = 2$ (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 $d = 1$, though that method doesn't easily extend to higher dimensions.

We first prove a Lemma, which is Helly's Theorem for $d=2, n = d+2$.

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 $X_1, X_2, X_3, X_4$. Define $a_i$ to be a common point of the three sets which do not include $X_i$. Now, consider the configuration of these 4 pointa.

1. If the convex hull of these 4 points is a triangle, WLOG let $a_1$ be in the interior. Then since $a_2, a_3, a_4$ is within $X_1$, hence $a_1$ is within the triangle given by $a_2, a_3, a_4$ and hence is within $X_1$. So $a_1$ is in all four sets.

2. If the convex hull of these 4 points is a convex quadrilateral, WLOG let the points be ordered as $a_1, a_2, a_3, a_4$. Now consider the diagonals $\overline{a_1 a_3}$ and $\overline { a_2, a_4 }$. Since it is a convex quadrilateral, they intersect at a point $p$. Then, since $p \in \overline{a_1 a_3}$, hence $p$ is in sets $X_2$ and $X_4$. Similarly, since $p \in \overline{a_2 a_4}$, hence $p$ is in sets $X_1$ and $X_3$. Thus, $p$ is in all four sets. $_\square$.

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 $n = 3$ is trivially true. The base case $n = 4$ is the above Lemma.

For the induction step, suppose the theorem holds for some $k$. Given any set of $k+1$ subsets $X_1, X_2, \ldots X_k, X_{k+1}$, consider the set of $k$ subsets $Y_1 = X_1 \cap X_{k+1}, Y_2 = X_2 \cap X_{k+1}, \ldots, Y_k = X_k \cap X_{k+1}$. From the intersection property, we know that $Y_i$ is a convex set for all $i$.

Now, consider the intersection of any 3 sets. We have

$Y_p \cap Y_q \cap Y_r = X_p \cap X_q \cap X_r \cap X_{k+1},$

which is nonempty by the Lemma. Applying the induction hypothesis to the sets $Y_i$, we conclude that the intersection of all sets $Y_i$ is non-empty. But since $\cap X_i = \cap Y_i$, it follows that the interesction of $X_i$ is also non-empty. $_ \square$

The requirement of a finite collection of subsets is necessary. For example, on the number line, the collection of sets $\{ [n, \infty ) \}$ 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.

Worked Examples

1. Prove Helly's Theorem for $d = 1$, 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. $_ \square$

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.

2. Find a collection of 3 sets in the plane ($d = 2$ ), such that every 2 of them intersect, but all 3 of them do not intersect.

Solution: Let $ABC$ be a non-degenerate triangle. Let the sets be the line segments $AB, BC, CA$. Clearly, any 2 of them intersect (at a vertex), and the 3 of them do not intersect. $_ \square$

Note: This shows that the requirement that every $d+1$ sets have a non-empty intersection is strict. Do you see how to generalize this counter example to all $d$?

3. Let $x_1, x_2, \ldots x_n$ be a finite set of points in the plane, such that the distance between any 2 points is less than 1. Show that there exists a disk of radius 1 which covers all of these points.

Solution: Let $X_i$ be disks of radius 1 with center $x_i$. Then, every 3 of these disks $X_i, X_j,$ and $X_k$ have a non-empty intersection, since we know that the point $x_i$ lies in $X_i \cap X_j \cap X_k$. Hence, by Helly's Theorem, there is a point $x$ which lies in $\cap X_i$, which means that the distance between $x$ and $x_i$ is less than 1. Hence, the disk $X$ of radius 1 with center $x$ covers all of these points. $_\square$

Note: Can you improve on this, and use a disk of smaller radius?