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 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 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?
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:
*italics*
or_italics_
**bold**
or__bold__
paragraph 1
paragraph 2
[example link](https://brilliant.org)
> This is a quote
\(
...\)
or\[
...\]
to ensure proper formatting.2 \times 3
2^{34}
a_{i-1}
\frac{2}{3}
\sqrt{2}
\sum_{i=1}^3
\sin \theta
\boxed{123}
Comments
Thanks Calvin, very nice article. :)
Question 2
I'm not sure about this, but can't we do better than radius 1?
Suppose that n≥3, and consider three distinct vertices xi,xj,xk, where 1≤i<j<k≤n. Since ∣xi−xj∣∣xj−xk∣∣xk−xi∣≤≤≤a=i∑j−1∣xa−xa+1∣a=j∑k−1∣xa−xa+1∣a=k∑n−1∣xa−xa+1∣+∣xn−x1∣+a=1∑i−1∣xa−xa+1∣ and hence ∣xi−xj∣+∣xj−xk∣+∣xk−xi∣≤a=1∑n−1∣xa−xa+1∣+∣xn−x1∣=2 the triangle formed by xi,xj,xk 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≤a+b, and hence 2c≤a+b+c≤2, so that a,b,c≤1. Thus we deduce that any two of the points x1,x2,…,xn are at most 1 apart. Question 1 tells us that all the vertices sit within a circle of radius 31. Since a circle is convex, the convex hull of the vertices, which certainly includes the polygon itself, sits inside a circle of radius 31.
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 ε>0 we can find N points x1,x2,…,xN on the curve C such that any point on C is within ε of one of the points xj. Then x1,x2,…,xN form a polygon with perimeter no greater than 2, and hence these N points all sit within a circle of radius 31, with some centre y. Thus all points on C lie inside the circle centre y and radius 31+ε.
Since we can choose ε>0 freely, we can fit any such closed curve inside a circle of radius r for any r>31.
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 21, 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).
Log in to reply
Suppose that ABC is a triangle with perimeter 2, and suppose that a is the longest of the three sides. Then 32≤a≤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 21 contains the entire "triangle". Suppose therefore that 32≤a<1.
We know that A must lie on (part of) an ellipse with foci B and C; if this ellipse has equation α2x2+β2y2=1 with eccentricity e, so that β2=α2(1−e2), then the foci B,C have coordinates (±αe,0), and the fact that ABC has perimeter 2 tells us that 2α+2αe=2, so that α(1+e)=1. Thus α=1+e1 and β=1+e1−e. Since a=2αe=1+e2e, the fact that 32≤a<1 tells us that 21≤e<1.
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αe and BX=CY=2α(1−e). This arrangement of X and Y is possible because e≥21. Consider the isosceles triangle XBC and the angle θ. By the Cosine Rule: cosθ=2×4α2e24α2e2+4α2e2−4α2(1−e)2=2e2e2+2e−1 and hence sin2θ==1−4e4(e2+2e−1)2=4e4(2e2+e2+2e−1)(2e2−e2−2e+1)4e4(1−e)2(3e2+2e−1) Using the Sine Rule, we obtain that the radius R of the circumcircle of XBC is R=sinθα(1−e)=(1+e)3e2+2e−12e2 Thus 41−R2=4(1+e)2(3e2+2e−1)(1+e)2(3e2+2e−1)−16e4=4(e+1)3(3e−1)(1−e)(13e3+5e2−e−1) It is clear that 13e3+5e2−e−1≥0 for all e≥21, and hence we deduce that R≤21 for all 21≤e<1.
Thus the circumcircle of XBC has radius at most 21. 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 (αcosϕ,βsinϕ), for some 0<ϕ0≤ϕ≤π−ϕ0<π. Note that ϕ=π−ϕ0 at the point X, and ϕ=ϕ0 at the point Y, so that αcosϕ0=2αecosθ−αe, and hence cosϕ0=e2e−1.
Suppose that Φ is the angle ∠BPC. Using the Cosine Rule on the triangle BPC, we have 4e2α20==α2(1+ecosϕ)2+α2(1−ecosϕ)2−2α2(1−e2cos2ϕ)cosΦ1+e2cos2ϕ−2e2−(1−e2cos2ϕ)cosΦ Differentiating with respect to ϕ: 0dϕdΦ==−2e2sinϕcosϕ−2e2sinϕcosϕcosΦ+(1−e2cos2ϕ)sinΦdϕdΦ(1−e2cos2ϕ)sinΦ2e2sinϕcosϕ(1+cosΦ)=1−e2cos2ϕ2e2sinϕcosϕcot21Φ It is clear that 0<Φ<π on the elliptical arc XY, and hence we deduce that dϕdΦ is positive for ϕ<21π, and negative for ϕ>21π. Since Φ(ϕ0)=∠BYC=21π−21θ=∠BXC=Φ(π−ϕ0) we deduce that Φ≥21π−21θ 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 21. 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 21.
Question 1
The result is trivial if n≤2, so suppose that n≥3. Let the points be x1,x2,…,xn. For any 1≤j≤n let Aj={y∈R2:∣y−xj∣≤31} The sets A1,A2,…,An are convex subsets of R2.
Consider any three of these sets, say Ai,Aj,Ak where 1≤i<j<k≤n. The points xi,xj,xk 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 31 of each of xi,xj,xk, and hence y belongs to each of Ai,Aj,Ak. Hence Ai∩Aj∩Ak=∅. By Helly's Theorem, this implies that j=1⋂nAj=∅ If we choose z in this common intersection, then z is the centre of a circle of radius 31 which contains all of x1,x2,…,xn.
Log in to reply
That was my first thought too, but I'm not sure about this statement:
For example, if AB=(0,0), BC=(r,0) and CA=(rcosθ,rsinθ) where r is slightly smaller than 1 and θ 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 AiAjAk and show that OAi=OAj=OAk=R<31.
Log in to reply
Good point (I presume you mean that (0,0), etc. are the coordinates of A,B,C. I like your alternative idea. Suppose that ∠A≥60∘ (at least one angle must be this big). Then, by the Sine Rule, R=2sinA∣BC∣≤3∣BC∣≤31 where R is the outradius, and we are done.
Log in to reply
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 ∠ABC=179.9∘ is very large. This is almost like a straight line segment, and hence the circumradius is extremely large and thus not smaller than 31. The mistake in your calculation is assuming that ∠A≤90∘, and in my counter-example above, I have ∠A=179.9∘ and hence sinA=0.00175 which gives R≈57.
Log in to reply
Let ∠A be the largest in the triangle. It must be at least 60∘.
If ∠A lies between 60∘ and 120∘, then sinA≥213, and the outradius argument works.
If ∠A is greater than 120∘, then both ∠B and ∠C are less than 60∘, 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.
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.
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.
For 1. I'd start with making circles C1,C2,⋯,Cn 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.
Log in to reply
Please read the question carefully. The disk is of radius 31, 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.
Log in to reply
I can see that the 31 comes from the circumscribed circle of a equilateral triangle :)
I just haven't worked out how to get there :p