Helly's Theorem

This note has been used to help create the Helly's Theorem wiki

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 XX is convex, if for every pair of points pp and qq in XX, the line segment pq\overline{pq} lies within XX. 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 X1X_1 and X2X_2 . Let X=X1X2 X = X_1 \cap X_2 . Take any 2 points pp and qq in XX. These points lie in X1X_1 (and in X2X_2 ). By definition of convex, the line segment pq \overline{pq} lies in X1X_1 (and in X2 X_2 ). Hence, pq \overline{pq} lies in their intersection, which is XX. Thus, XX is convex. _\square.

For those who are familiar with convex functions, we say that a function f(x) 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 X1,X2,,Xn X_1, X_2, \ldots, X_n is a collection of convex sets in Rd \mathbb{R} ^d , with n>d n > d . If the intersection of every d+1 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 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 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 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 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 X1,X2,X3,X4 X_1, X_2, X_3, X_4 . Define ai a_i to be a common point of the three sets which do not include Xi X_i . Now, consider the configuration of these 4 pointa.

  1. If the convex hull of these 4 points is a triangle, WLOG let a1 a_1 be in the interior. Then since a2,a3,a4 a_2, a_3, a_4 is within X1X_1, hence a1 a_1 is within the triangle given by a2,a3,a4 a_2, a_3, a_4 and hence is within X1X_1. So a1 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 a1,a2,a3,a4 a_1, a_2, a_3, a_4 . Now consider the diagonals a1a3 \overline{a_1 a_3} and a2,a4 \overline { a_2, a_4 } . Since it is a convex quadrilateral, they intersect at a point pp. Then, since pa1a3 p \in \overline{a_1 a_3} , hence pp is in sets X2 X_2 and X4X_4 . Similarly, since pa2a4 p \in \overline{a_2 a_4} , hence pp is in sets X1 X_1 and X3X_3 . Thus, pp 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 n = 3 is trivially true. The base case n=4 n = 4 is the above Lemma.

For the induction step, suppose the theorem holds for some kk. Given any set of k+1k+1 subsets X1,X2,Xk,Xk+1 X_1, X_2, \ldots X_k, X_{k+1}, consider the set of kk subsets Y1=X1Xk+1,Y2=X2Xk+1,,Yk=XkXk+1 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 Yi Y_i is a convex set for all ii.

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

YpYqYr=XpXqXrXk+1, 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 YiY_i, we conclude that the intersection of all sets YiY_i is non-empty. But since Xi=Yi \cap X_i = \cap Y_i , it follows that the interesction of XiX_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,)} \{ [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=1d = 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=2d = 2 ), such that every 2 of them intersect, but all 3 of them do not intersect.

Solution: Let ABCABC be a non-degenerate triangle. Let the sets be the line segments AB,BC,CAAB, 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 d+1 sets have a non-empty intersection is strict. Do you see how to generalize this counter example to all dd?


3. Let x1,x2,xnx_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 Xi X_i be disks of radius 1 with center xi x_i . Then, every 3 of these disks Xi,Xj, X_i, X_j, and Xk X_k have a non-empty intersection, since we know that the point xi x_i lies in XiXjXk X_i \cap X_j \cap X_k . Hence, by Helly's Theorem, there is a point xx which lies in Xi \cap X_i , which means that the distance between xx and xix_i is less than 1. Hence, the disk XX of radius 1 with center xx covers all of these points. _\square

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

Note by Calvin Lin
7 years, 4 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}


There are no comments in this discussion.


Problem Loading...

Note Loading...

Set Loading...