Helly's Theorem

This week, we learn about Helly's Theorem, a surprising result from combinatorial geometry which explains how convex sets may intersect each other.

How would you use Helly's Theorem to solve the following?

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 $\frac{1}{\sqrt{3}}$ which covers all of these points.

Show that any polygon with perimeter 2 can be covered with a disk of radius 1.
What if the edges do not need to be straight lines?

#KeyTechniques

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.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered 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"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

Thanks Calvin, very nice article. :)

C Lim - 7 years, 8 months ago

Question 2

I'm not sure about this, but can't we do better than radius $1$ ?

Suppose that $n \ge 3$ , and consider three distinct vertices $x_i,x_j,x_k$ , where $1 \le i < j < k \le n$ . Since $\begin{array}{rcl} |x_i - x_j| & \le & \displaystyle\sum_{a=i}^{j-1} |x_a - x_{a+1}| \\ |x_j - x_k| & \le & \displaystyle\sum_{a=j}^{k-1} |x_a - x_{a+1}| \\ |x_k - x_i| & \le & \displaystyle\sum_{a=k}^{n-1} |x_a - x_{a+1}| + |x_n - x_1| + \sum_{a=1}^{i-1}|x_a-x_{a+1}| \end{array}$ and hence $|x_i - x_j| + |x_j - x_k| + |x_k - x_i| \; \le \; \sum_{a=1}^{n-1}|x_a - x_{a+1}| + |x_n - x_1| \; = \; 2$ the triangle formed by $x_i,x_j,x_k$ has perimeter at most $2$ . Suppose that the lengths of the sides of that triangle are $a,b,c$ , and that $c$ is the largest side. Then $c \le a + b$ , and hence $2c \le a + b + c \le 2$ , so that $a,b,c \le 1$ . Thus we deduce that any two of the points $x_1,x_2,\ldots,x_n$ are at most $1$ apart. Question 1 tells us that all the vertices sit within a circle of radius $\tfrac{1}{\sqrt{3}}$ . Since a circle is convex, the convex hull of the vertices, which certainly includes the polygon itself, sits inside a circle of radius $\tfrac{1}{\sqrt{3}}$ .

As for the more general case, we are asking if a closed curve $C$ of length $2$ sits inside a circle of radius $1$ . To be able to define the perimeter of the curve, let us make the curve $C$ be continuous and indeed piecewise continuously differentiable. By uniform continuity, for any $\varepsilon > 0$ we can find $N$ points $x_1,x_2,\ldots,x_N$ on the curve $C$ such that any point on $C$ is within $\varepsilon$ of one of the points $x_j$ . Then $x_1,x_2,\ldots,x_N$ form a polygon with perimeter no greater than $2$ , and hence these $N$ points all sit within a circle of radius $\tfrac{1}{\sqrt{3}}$ , with some centre $y$ . Thus all points on $C$ lie inside the circle centre $y$ and radius $\tfrac{1}{\sqrt{3}} + \varepsilon$ .

Since we can choose $\varepsilon>0$ freely, we can fit any such closed curve inside a circle of radius $r$ for any $r > \tfrac{1}{\sqrt{3}}$ .

Mark Hennings - 7 years, 8 months ago

Yes, we can do better than radius 1. Similar to the first question, the idea is to lead you on to thinking about how to approach such a situation using Helly's Theorem, which isn't a common concept that most members would have come across. I started with a large value to make the arguments easier.

For this question, I believe that the best bound is a circle of radius $\frac{1}{2}$ , i.e. diameter 1. Appealing to the first question doesn't get it down so tight, because the equilateral triangle is the equality case in question 1, but has perimeter greater than 2. Instead, the equality case in question 2, is the unit line segment (with a limiting argument if you wish to stay with polygons).

Calvin Lin Staff - 7 years, 8 months ago

Suppose that $ABC$ is a triangle with perimeter $2$ , and suppose that $a$ is the longest of the three sides. Then $\tfrac23 \le a \le 1$ . The case $a=1$ is the trivial case where the triangle collapses to a straight line, with $A$ being the midpoint of $BC$ . In that case the circle centre $A$ and radius $\tfrac12$ contains the entire "triangle". Suppose therefore that $\tfrac23 \le a < 1$ .

We know that $A$ must lie on (part of) an ellipse with foci $B$ and $C$ ; if this ellipse has equation $\frac{x^2}{\alpha^2} + \frac{y^2}{\beta^2} \; = \; 1$ with eccentricity $e$ , so that $\beta^2 = \alpha^2(1 - e^2)$ , then the foci $B,C$ have coordinates $(\pm\alpha e,0)$ , and the fact that $ABC$ has perimeter $2$ tells us that $2\alpha + 2\alpha e \,=\, 2$ , so that $\alpha(1+e) = 1$ . Thus $\alpha = \tfrac{1}{1+e}$ and $\beta = \sqrt{\tfrac{1-e}{1+e}}$ . Since $a = 2\alpha e = \tfrac{2e}{1+e}$ , the fact that $\tfrac23 \le a < 1$ tells us that $\tfrac12 \le e < 1$ .

alternate<em>text alternatetext

Of course $a$ still has to be the longest side, and so $A$ can only lie on a portion of the ellipse --- that portion of the ellipse between $X$ and $Y$ (or its mirror image in the $x$ -axis) where $BY = CX = a = 2\alpha e$ and $BX = CY = 2\alpha(1-e)$ . This arrangement of $X$ and $Y$ is possible because $e \ge \tfrac12$ . Consider the isosceles triangle $XBC$ and the angle $\theta$ . By the Cosine Rule: $\cos\theta \; = \; \frac{4\alpha^2 e^2 + 4\alpha^2e^2 - 4\alpha^2(1-e)^2}{2\times 4\alpha^2e^2} \; = \; \frac{e^2 + 2e - 1}{2e^2}$ and hence $\begin{array}{rcl} \sin^2\theta & = & \displaystyle1 - \frac{(e^2 + 2e - 1)^2}{4e^4} \; = \; \frac{(2e^2 + e^2 + 2e - 1)(2e^2 - e^2 - 2e + 1)}{4e^4} \\ & = & \displaystyle\frac{(1-e)^2(3e^2 + 2e - 1)}{4e^4} \end{array}$ Using the Sine Rule, we obtain that the radius $R$ of the circumcircle of $XBC$ is $R \; = \; \frac{\alpha(1-e)}{\sin\theta} \; = \; \frac{2e^2}{(1+e)\sqrt{3e^2+2e-1}}$ Thus $\begin{array}{rcl} \tfrac14 - R^2 & = & \displaystyle\frac{(1+e)^2(3e^2+2e-1) - 16e^4}{4(1+e)^2(3e^2+2e-1)} \; = \; \frac{(1-e)(13e^3 + 5e^2 - e - 1)}{4(e+1)^3(3e-1)} \end{array}$ It is clear that $13e^3 + 5e^2 - e - 1 \ge 0$ for all $e \ge \tfrac12$ , and hence we deduce that $R \le \tfrac12$ for all $\tfrac12 \le e < 1$ .

Thus the circumcircle of $XBC$ has radius at most $\tfrac12$ . By symmetry it is also the circumcircle of the triangle $YBC$ . I claim that the entirety of the elliptical arc $XY$ lies inside this circle.

To prove this, suppose that $P$ is a point on the elliptical arc $XY$ . Then $P$ has coordinates $(\alpha\cos\phi, \beta\sin\phi)$ , for some $0 < \phi_0 \le \phi \le \pi - \phi_0 < \pi$ . Note that $\phi=\pi-\phi_0$ at the point $X$ , and $\phi=\phi_0$ at the point $Y$ , so that $\alpha\cos\phi_0 = 2\alpha e\cos\theta - \alpha e$ , and hence $\cos\phi_0 = \tfrac{2e-1}{e}$ .

Suppose that $\Phi$ is the angle $\angle BPC$ . Using the Cosine Rule on the triangle $BPC$ , we have $\begin{array}{rcl} 4e^2\alpha^2 & = & \alpha^2(1+e\cos\phi)^2 + \alpha^2(1-e\cos\phi)^2 - 2\alpha^2(1-e^2\cos^2\phi)\cos\Phi \\ 0 & = & 1 + e^2\cos^2\phi - 2e^2 - (1-e^2\cos^2\phi)\cos\Phi \end{array}$ Differentiating with respect to $\phi$ : $\begin{array}{rcl} 0 & = & -2e^2\sin\phi\cos\phi - 2e^2\sin\phi\cos\phi\cos\Phi + (1 - e^2\cos^2\phi)\sin\Phi\frac{d\Phi}{d\phi} \\ \frac{d\Phi}{d\phi} & = & \displaystyle\frac{2e^2\sin\phi\cos\phi(1+\cos\Phi)}{(1 - e^2\cos^2\phi)\sin\Phi} \; = \; \frac{2e^2\sin\phi\cos\phi\cot\frac12\Phi}{1 - e^2\cos^2\phi} \end{array}$ It is clear that $0 < \Phi < \pi$ on the elliptical arc $XY$ , and hence we deduce that $\frac{d\Phi}{d\phi}$ is positive for $\phi < \tfrac12\pi$ , and negative for $\phi > \tfrac12\pi$ . Since $\Phi(\phi_0) \;= \; \angle BYC \; = \; \tfrac12\pi - \tfrac12\theta \; = \; \angle BXC \; = \; \Phi(\pi - \phi_0)$ we deduce that $\Phi \ge \tfrac12\pi - \tfrac12\theta$ for all points $P$ on the elliptical arc $XY$ . Since $P$ subtends an angle on the line $BC$ at least as big as the angle subtended by the points $X$ and $Y$ , and therefore by any point in the section of the circumcircle of $BCX$ that lies above the $x$ -axis, we deduce that $P$ must in fact lie inside that circle.

Thus we have shown that any triangle of perimeter $2$ lies inside some circle of radius $\tfrac12$ . This is the technical result we need to deduce what is the optimal version of Question 2, that any polygon with perimeter $2$ lies inside a circle of radius $\tfrac12$ .

Mark Hennings - 7 years, 7 months ago

Question 1

The result is trivial if $n \le 2$ , so suppose that $n \ge 3$ . Let the points be $x_1,x_2,\ldots,x_n$ . For any $1 \le j \le n$ let $A_j \; = \; \big\{ y \in \mathbb{R}^2 \,:\, |y-x_j| \le \tfrac{1}{\sqrt{3}} \big\}$ The sets $A_1,A_2,\ldots,A_n$ are convex subsets of $\mathbb{R}^2$ .

Consider any three of these sets, say $A_i,A_j,A_k$ where $1 \le i < j < k \le n$ . The points $x_i,x_j,x_k$ are all within $1$ of each other, and hence all lie within an equilateral triangle of side $1$ . If we let $y$ be the centre of that equilateral triangle, then $y$ is within $\tfrac{1}{\sqrt{3}}$ of each of $x_i,x_j,x_k$ , and hence $y$ belongs to each of $A_i, A_j, A_k$ . Hence $A_i \cap A_j \cap A_k \neq \varnothing$ . By Helly's Theorem, this implies that $\bigcap_{j=1}^n A_j \, \neq \, \varnothing$ If we choose $z$ in this common intersection, then $z$ is the centre of a circle of radius $\tfrac{1}{\sqrt{3}}$ which contains all of $x_1,x_2,\ldots,x_n$ .

Mark Hennings - 7 years, 8 months ago

That was my first thought too, but I'm not sure about this statement:

if $AB, BC, CA < 1$ , then $ABC$ is contained in an equilateral triangle of side 1.

For example, if $AB = (0, 0)$ , $BC = (r,0)$ and $CA = (r \cos \theta, r\sin \theta)$ where $r$ is slightly smaller than 1 and $\theta$ is really small, I don't think they can be contained in such a triangle.

An alternative would be to take the circumcentre $O$ of $A_i A_j A_k$ and show that $OA_i = OA_j = OA_k = R < \frac 1 {\sqrt 3}$ .

C Lim - 7 years, 8 months ago

Good point (I presume you mean that $(0,0)$ , etc. are the coordinates of $A,B,C$ . I like your alternative idea. Suppose that $\angle A \ge 60^\circ$ (at least one angle must be this big). Then, by the Sine Rule, $R \; = \; \frac{|BC|}{2\sin A} \; \le \; \frac{|BC|}{\sqrt{3}} \; \le \; \tfrac{1}{\sqrt{3}}$ where $R$ is the outradius, and we are done.

Mark Hennings - 7 years, 8 months ago

@Mark Hennings – The first question requires you to be very careful with the technical details of the proof. There are 2 potential issues that needed to be dealt with:

C L. pointed out the first one, which is that "not every such triangle can fit into an equilateral triangle".

For your circumradius (out radius) argument, consider triangle $ABC$ where $AB=BC = 0.1$ and $\angle ABC = 179.9^\circ$ is very large. This is almost like a straight line segment, and hence the circumradius is extremely large and thus not smaller than $\frac{ 1 } { \sqrt{3} }$ . The mistake in your calculation is assuming that $\angle A \leq 90^\circ$ , and in my counter-example above, I have $\angle A = 179.9^\circ$ and hence $\sin A = 0.00175$ which gives $R \approx 57$ .

Calvin Lin Staff - 7 years, 8 months ago

@Calvin Lin – OK, we can fix both of these by bringing back my first idea.

Let $\angle A$ be the largest in the triangle. It must be at least $60^\circ$ .

If $\angle A$ lies between $60^\circ$ and $120^\circ$ , then $\sin A \ge \tfrac12\sqrt{3}$ , and the outradius argument works.

If $\angle A$ is greater than $120^\circ$ , then both $\angle B$ and $\angle C$ are less than $60^\circ$ , and hence the point $A$ must lie within an equilateral triangle with base $BC$ . Thus the three points sit inside an equilateral triangle of side at most $1$ .

Mark Hennings - 7 years, 8 months ago

Let (x'a) be disks of radius 1/√(3)with center (X'a). Then, every 3 of these disks x'a , x'b & x'c have a non-empty intersection, since we know that the point (X'a) lies in intersect(x'a)intersect (x'b)intersect(x'c) . Hence, by Helly's Theorem, there is a point (X) which lies in intersect (x'a), which means that the distance between(X) and (X'a) is less than 1. Hence, the disk(x'a) of radius 1/√(3)with center (X'a) covers all of these points.

Mahdi Al-kawaz - 7 years, 8 months ago

Why must the point (X'a) lies in intersect(x'a)intersect (x'b)intersect(x'c)?

What if (X'a) is distance 1 away from (X'c)? Then (x'c) would not contain (X'a). The argument that you are using works for circles of radius 1, which was the case of Worked Example 3.

Calvin Lin Staff - 7 years, 8 months ago

For 1. I'd start with making circles $C_{1}, C_{2}, \cdots, C_{n}$ around our points, all with radius 1. Since all points are within all circles, we also have that all points lie in the intersection of all of them. But this is not Helly's Theorem.

Ton de Moree - 7 years, 8 months ago

Please read the question carefully. The disk is of radius $\frac{1}{ \sqrt{3}}$ , which is much less than 1.

The post deals with the case with radius 1 as a very simple application because this case is immediately obvious like you pointed out.

Calvin Lin Staff - 7 years, 8 months ago

I can see that the $\frac{1}{\sqrt{3}}$ comes from the circumscribed circle of a equilateral triangle :)

I just haven't worked out how to get there :p

Ton de Moree - 7 years, 8 months ago

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$