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?

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

  2. 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?

Note by Calvin Lin
6 years, 1 month ago

No vote yet
18 votes

  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}

Comments

Sort by:

Top Newest

Question 2

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

Suppose that n3n \ge 3, and consider three distinct vertices xi,xj,xkx_i,x_j,x_k, where 1i<j<kn1 \le i < j < k \le n. Since xixja=ij1xaxa+1xjxka=jk1xaxa+1xkxia=kn1xaxa+1+xnx1+a=1i1xaxa+1 \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 xixj+xjxk+xkxi    a=1n1xaxa+1+xnx1  =  2 |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 xi,xj,xkx_i,x_j,x_k has perimeter at most 22. Suppose that the lengths of the sides of that triangle are a,b,ca,b,c, and that cc is the largest side. Then ca+bc \le a + b, and hence 2ca+b+c22c \le a + b + c \le 2, so that a,b,c1a,b,c \le 1. Thus we deduce that any two of the points x1,x2,,xnx_1,x_2,\ldots,x_n are at most 11 apart. Question 1 tells us that all the vertices sit within a circle of radius 13\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 13\tfrac{1}{\sqrt{3}}.

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

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

Mark Hennings - 6 years, 1 month ago

Log in to reply

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 12 \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 - 6 years, 1 month ago

Log in to reply

Suppose that ABCABC is a triangle with perimeter 22, and suppose that aa is the longest of the three sides. Then 23a1\tfrac23 \le a \le 1. The case a=1a=1 is the trivial case where the triangle collapses to a straight line, with AA being the midpoint of BCBC. In that case the circle centre AA and radius 12\tfrac12 contains the entire "triangle". Suppose therefore that 23a<1\tfrac23 \le a < 1.

We know that AA must lie on (part of) an ellipse with foci BB and CC; if this ellipse has equation x2α2+y2β2  =  1 \frac{x^2}{\alpha^2} + \frac{y^2}{\beta^2} \; = \; 1 with eccentricity ee, so that β2=α2(1e2)\beta^2 = \alpha^2(1 - e^2), then the foci B,CB,C have coordinates (±αe,0)(\pm\alpha e,0), and the fact that ABCABC has perimeter 22 tells us that 2α+2αe=22\alpha + 2\alpha e \,=\, 2, so that α(1+e)=1\alpha(1+e) = 1. Thus α=11+e\alpha = \tfrac{1}{1+e} and β=1e1+e\beta = \sqrt{\tfrac{1-e}{1+e}}. Since a=2αe=2e1+ea = 2\alpha e = \tfrac{2e}{1+e}, the fact that 23a<1\tfrac23 \le a < 1 tells us that 12e<1\tfrac12 \le e < 1.

alternate<em>text alternatetext

Of course aa still has to be the longest side, and so AA can only lie on a portion of the ellipse --- that portion of the ellipse between XX and YY (or its mirror image in the xx-axis) where BY=CX=a=2αeBY = CX = a = 2\alpha e and BX=CY=2α(1e)BX = CY = 2\alpha(1-e). This arrangement of XX and YY is possible because e12e \ge \tfrac12. Consider the isosceles triangle XBCXBC and the angle θ\theta. By the Cosine Rule: cosθ  =  4α2e2+4α2e24α2(1e)22×4α2e2  =  e2+2e12e2 \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 sin2θ=1(e2+2e1)24e4  =  (2e2+e2+2e1)(2e2e22e+1)4e4=(1e)2(3e2+2e1)4e4\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 RR of the circumcircle of XBCXBC is R  =  α(1e)sinθ  =  2e2(1+e)3e2+2e1 R \; = \; \frac{\alpha(1-e)}{\sin\theta} \; = \; \frac{2e^2}{(1+e)\sqrt{3e^2+2e-1}} Thus 14R2=(1+e)2(3e2+2e1)16e44(1+e)2(3e2+2e1)  =  (1e)(13e3+5e2e1)4(e+1)3(3e1) \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 13e3+5e2e1013e^3 + 5e^2 - e - 1 \ge 0 for all e12e \ge \tfrac12, and hence we deduce that R12R \le \tfrac12 for all 12e<1\tfrac12 \le e < 1.

Thus the circumcircle of XBCXBC has radius at most 12\tfrac12. By symmetry it is also the circumcircle of the triangle YBCYBC. I claim that the entirety of the elliptical arc XYXY lies inside this circle.

To prove this, suppose that PP is a point on the elliptical arc XYXY. Then PP has coordinates (αcosϕ,βsinϕ)(\alpha\cos\phi, \beta\sin\phi), for some 0<ϕ0ϕπϕ0<π0 < \phi_0 \le \phi \le \pi - \phi_0 < \pi. Note that ϕ=πϕ0\phi=\pi-\phi_0 at the point XX, and ϕ=ϕ0\phi=\phi_0 at the point YY, so that αcosϕ0=2αecosθαe\alpha\cos\phi_0 = 2\alpha e\cos\theta - \alpha e, and hence cosϕ0=2e1e\cos\phi_0 = \tfrac{2e-1}{e}.

Suppose that Φ\Phi is the angle BPC\angle BPC. Using the Cosine Rule on the triangle BPCBPC, we have 4e2α2=α2(1+ecosϕ)2+α2(1ecosϕ)22α2(1e2cos2ϕ)cosΦ0=1+e2cos2ϕ2e2(1e2cos2ϕ)cosΦ \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: 0=2e2sinϕcosϕ2e2sinϕcosϕcosΦ+(1e2cos2ϕ)sinΦdΦdϕdΦdϕ=2e2sinϕcosϕ(1+cosΦ)(1e2cos2ϕ)sinΦ  =  2e2sinϕcosϕcot12Φ1e2cos2ϕ \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<Φ<π0 < \Phi < \pi on the elliptical arc XYXY, and hence we deduce that dΦdϕ\frac{d\Phi}{d\phi} is positive for ϕ<12π\phi < \tfrac12\pi, and negative for ϕ>12π\phi > \tfrac12\pi. Since Φ(ϕ0)  =  BYC  =  12π12θ  =  BXC  =  Φ(πϕ0) \Phi(\phi_0) \;= \; \angle BYC \; = \; \tfrac12\pi - \tfrac12\theta \; = \; \angle BXC \; = \; \Phi(\pi - \phi_0) we deduce that Φ12π12θ\Phi \ge \tfrac12\pi - \tfrac12\theta for all points PP on the elliptical arc XYXY. Since PP subtends an angle on the line BCBC at least as big as the angle subtended by the points XX and YY, and therefore by any point in the section of the circumcircle of BCXBCX that lies above the xx-axis, we deduce that PP must in fact lie inside that circle.

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

Mark Hennings - 6 years ago

Log in to reply

Thanks Calvin, very nice article. :)

C Lim - 6 years, 1 month ago

Log in to reply

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 - 6 years, 1 month ago

Log in to reply

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 - 6 years, 1 month ago

Log in to reply

Question 1

The result is trivial if n2n \le 2, so suppose that n3n \ge 3. Let the points be x1,x2,,xnx_1,x_2,\ldots,x_n. For any 1jn1 \le j \le n let Aj  =  {yR2:yxj13} A_j \; = \; \big\{ y \in \mathbb{R}^2 \,:\, |y-x_j| \le \tfrac{1}{\sqrt{3}} \big\} The sets A1,A2,,AnA_1,A_2,\ldots,A_n are convex subsets of R2\mathbb{R}^2.

Consider any three of these sets, say Ai,Aj,AkA_i,A_j,A_k where 1i<j<kn1 \le i < j < k \le n. The points xi,xj,xkx_i,x_j,x_k are all within 11 of each other, and hence all lie within an equilateral triangle of side 11. If we let yy be the centre of that equilateral triangle, then yy is within 13\tfrac{1}{\sqrt{3}} of each of xi,xj,xkx_i,x_j,x_k, and hence yy belongs to each of Ai,Aj,AkA_i, A_j, A_k. Hence AiAjAkA_i \cap A_j \cap A_k \neq \varnothing. By Helly's Theorem, this implies that j=1nAj \bigcap_{j=1}^n A_j \, \neq \, \varnothing If we choose zz in this common intersection, then zz is the centre of a circle of radius 13\tfrac{1}{\sqrt{3}} which contains all of x1,x2,,xnx_1,x_2,\ldots,x_n.

Mark Hennings - 6 years, 1 month ago

Log in to reply

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

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

For example, if AB=(0,0)AB = (0, 0), BC=(r,0)BC = (r,0) and CA=(rcosθ,rsinθ)CA = (r \cos \theta, r\sin \theta) where rr 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 OO of AiAjAkA_i A_j A_k and show that OAi=OAj=OAk=R<13OA_i = OA_j = OA_k = R < \frac 1 {\sqrt 3}.

C Lim - 6 years, 1 month ago

Log in to reply

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

Mark Hennings - 6 years, 1 month ago

Log in to reply

@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 ABCABC where AB=BC=0.1AB=BC = 0.1 and ABC=179.9 \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 13 \frac{ 1 } { \sqrt{3} } . The mistake in your calculation is assuming that A90 \angle A \leq 90^\circ , and in my counter-example above, I have A=179.9 \angle A = 179.9^\circ and hence sinA=0.00175 \sin A = 0.00175 which gives R57 R \approx 57 .

Calvin Lin Staff - 6 years, 1 month ago

Log in to reply

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

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

If A\angle A lies between 6060^\circ and 120120^\circ, then sinA123\sin A \ge \tfrac12\sqrt{3}, and the outradius argument works.

If A\angle A is greater than 120120^\circ, then both B\angle B and C\angle C are less than 6060^\circ, and hence the point AA must lie within an equilateral triangle with base BCBC. Thus the three points sit inside an equilateral triangle of side at most 11.

Mark Hennings - 6 years, 1 month ago

Log in to reply

For 1. I'd start with making circles C1,C2,,Cn 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 - 6 years, 1 month ago

Log in to reply

Please read the question carefully. The disk is of radius 13 \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 - 6 years, 1 month ago

Log in to reply

I can see that the 13 \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 - 6 years, 1 month ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...