Waste less time on Facebook — follow Brilliant.
×

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 \(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.

  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
3 years, 10 months ago

No vote yet
18 votes

Comments

Sort by:

Top Newest

Thanks Calvin, very nice article. :) C Lim · 3 years, 10 months ago

Log in to reply

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 · 3 years, 10 months ago

Log in to reply

@Mark Hennings 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 · 3 years, 10 months ago

Log in to reply

@Calvin Lin 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 · 3 years, 10 months 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 · 3 years, 10 months ago

Log in to reply

@Mahdi Al-kawaz 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 · 3 years, 10 months ago

Log in to reply

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 · 3 years, 10 months ago

Log in to reply

@Mark Hennings 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 · 3 years, 10 months ago

Log in to reply

@C Lim 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 · 3 years, 10 months 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 \(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 · 3 years, 10 months ago

Log in to reply

@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 · 3 years, 10 months ago

Log in to reply

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 · 3 years, 10 months ago

Log in to reply

@Ton De Moree 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 · 3 years, 10 months ago

Log in to reply

@Calvin Lin 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 · 3 years, 10 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...