Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The following problem has been attributed to Lebesgue. Let "set" denote any subset of the Euclidean plane. What is the greatest lower bound of the diameter of any set which contains a subset congruent to every set of diameter 1? There are a number of interesting geometric problems of this type. Is it possible that some of them may be difficult to solve because the solution is a real irrational number which (when expressed in decimal form) is not even recursive-and so cannot be approximated in the usual way?

share|improve this question

4 Answers 4

The question is still open. There are at least two versions. The most popular asks for the minimal-area convex subset of the plane such that every set with diameter 1 can be rotated and translated to fit inside it. Here is the best lower bound I know:

Their lower bound is 0.832, obtained through a rigorous computer-aided search for the convex set with the smallest area that contains a circle, equilateral triangle and pentagon of diameter 1.

Here is the best upper bound I know:

In 1920, Pál noted that a regular hexagon of area circumscribed around the unit circle does the job. This has area

$$ \sqrt{3}/2 \approx 0.86602540 $$

But in the same paper, he showed you could safely cut off two corners of this hexagon, defined by fitting a dodecagon circumscribed around the unit circle inside the hexagon. This brought the upper bound down to

$$ 2 - 2/\sqrt{3} \approx 0.84529946 $$

He guessed this solution was optimal.

In 1936, Sprague sliced tiny pieces of Pal's proposed solution and bring the upper bound down to

$$ \sim 0.84413770 $$

        Sprague
        (Image from Hansen's paper, added by J.O'Rourke.)

The big hexagon above is Pál's original solution. He then inscribed a regular dodecagon inside this, and showed that you can remove two of the resulting corners, say $B_1B_2B$ and $F_1F_2F,$ and get a smaller universal covering. But Sprague noticed that near $D$ you can also remove the part outside the circle with radius 1 centered at $B_1$, as well as the part outside the circle with radius 1 centered at $F_2.$

In 1975, Hansen showed you could slice off very tiny corners off Sprague's solution, each of which reduces the area by $6 \cdot 10^{-18}$.

In Hansen's 1992 paper, he did much better. He again sliced two corners off Sprague's solution, but now one reduces the area by a whopping $4 \cdot 10^{-11}$, while the other, the same shape as before, reduces the area by $6 \cdot 10^{-18}$.

One author, in a parody of the usual optimistic prophecies of accelerating progress, commented that

...progress on this question, which has been painfully slow in the past, may be even more painfully slow in the future.

In 1980, Duff considered nonconvex subsets of the plane with least area such that every set with diameter one can be rotated and translated to fit inside it. He found one with area

$$ \sim 0.84413570 $$

which is smaller than the best known convex solution:

  • G. F. D. Duff, A smaller universal cover for sets of unit diameter, C. R. Math. Acad. Sci. 2 (1980), 37--42.

I've written a slightly more detailed account with some pictures here:

If anyone knows of further progress on this puzzle, please let me know!

share|improve this answer
    
But the number in the 3rd display is bigger than the number in the 2nd display. –  Gerry Myerson Dec 8 '13 at 0:32
    
Fixed, I think - thanks! Somehow I'd put down the wrong figure for $2−2/\sqrt{3}$, and this cures the problem you mention. As for Sprague's improvement, I'm getting the figure second-hand. –  John Baez Dec 8 '13 at 7:37
    
You changed the second display, and then changed it back. $0.84413770$ is not an improvement on an upper bound of $0.8422038$, so what is going on here? Also, I edited in the ending page number for Brass-Sharifi, and you edited it out. –  Gerry Myerson Dec 8 '13 at 23:10
1  
I don't know how I screwed up that stuff. Sorry; it's my unfamiliarity with editing here. I fixed it up. –  John Baez Dec 9 '13 at 1:29

The problem has been studied for various groups $G$ of isometries of $\mathbb R^n$. A set $K\subset \mathbb R^n$ is called $G$-universal cover iff every set of diameter 1 is contained in $gK$ for some $g\in G$.

V. Makeev proved that the mean width of a $T_n$-universal cover is greater or equal to $\sqrt{2n/(2n+1)}$, where $T_n$ is the group of translations of $\mathbb R^n$. For $n=2$ the estimate is sharp; the perimeter of a $T_2$-universal cover $\geq 2\pi/\sqrt{3}$ (link).

M. Kovalev obtained a rather explicit description of all minimal $D_2$-universal covers, where $D_2$ is the group of all isometries of $\mathbb R^2$.

Theorem. Every minimal universal $D_2$-cover $K$ is star-shaped. There is a polar coordinate system (with the centre in $K$) such that $$\partial K=\{(\phi,\rho(\phi)):\ 0 < \phi\leq 2\pi\},$$ where $\rho=\rho(\phi)$ is Lipschitz and for any $\phi\in[0,2\pi]$ $$c^2\leq \rho(\phi) \leq 1 - c^2,\qquad c=1-1/\sqrt{3}.$$

share|improve this answer
2  
It's worth noting, for nonexperts, that "minimality" here means that the set $K$ doesn't contain a subset with the desired property. This is implied by, but does not imply, area minimization. Indeed, "minimal" solutions to the Lebesgue universal covering problem are known, while area-minimizing ones are not. –  John Baez Dec 8 '13 at 7:36

It's Lebesgue Minimal Problem. It's still open, though there are some bounds to the area of such set, for example there are lower bound for area $S\ge \frac{\pi}{8}+\frac{\sqrt{3}}{4}$

it's not hard to show that such set must have diameter larger or equal to $\frac{\sqrt{3}}{3}+\frac{1}{2}=1.077350...$ alt text

Our set must have a subsets congruent to the equlateral triangle with side 1(ABC) and to the circle with radius 0.5(with center O). If I - the incenter of triangle ABC, and $O \in BIC$, then consider point D which lies on the radius perpendicular to BC. Then $AD \ge AI+OD=1.077...$.

share|improve this answer
1  
You say $O \in BIC$ but your diagrams seems to have $O \notin BIC$. Still, it obeys $AD \ge AI + OD$. –  John Baez Dec 6 '13 at 8:13

As other answers have pointed out there are different versions and generalizations of Lebesgue's Universal Covering Problem. His original question from 1914 in a letter to Pál has been quoted as

"What is the smallest area of a convex set in the plane that contains a congruent copy of every planar set of unit diameter?" (see "Research Problems in Discrete Geometry" Brass, Moser, Pach.)

Variations of the question ask for the minimum diameter or perimeter. Sometimes the convexity condition is relaxed but an advantage of the convex case is that the existance of a universal cover with minimum area is then ensured by the Blaschke selection theorem. Congruence allows reflections as well as translations and rotations but in some statements of the problem reflections are not allowed. The universal covers found by Pál and improved by Sprague do not require reflections. The best known convex universal cover by Hansen from 1992 does require reflections. Hansen's area is 0.844137708435197570894066994 and Duff gave a smaller non-convex cover of 0.84413570 (see other answers for references)

However, it is possible to improve on these upper bounds as follows: Start with a regular hexagon circumscribed round a circle of diameter one. As Pál showed this is a universal cover. Pál considered the eight sided shape formed by removing two corners from this hexagon using cuts made with two lines tangent to the circle in such a way that the new edges are sides of a regular dodecagon inscribed in the hexagon. Now consider a more general case where the two cuts are still tangent to the circle and still at an angle of 60 degrees to each other but at a small angle $\sigma$ to the edges of a dodecahedron. The remaining shape is still a universal cover.

To see this consider the six triangles at the corners of the hexagon each outisde a line tangent to the circle and at the same slant angle away from the edge of a regualar dodecagon. In the diagram these are labelled A,B,C,D,E and F. Any shape of diameter one can be fitted inside the hexagon. The least distance between opposite triangles such as A and D is one, so the shape cannot be in the interior of both triangles. This is true for each of the three pairs of opposite triangles so the shape can only be inside the interior of at most three of these triangles. Each of the possible cases can be checked to see that the shape can then be rotated through some nultiple of sixty degrees around the centre so that it is still inside the hexagon but not inside the traingles E and C. Therefore the hexagon with these two triangles removed is a universal cover.

enter image description here

This cover can be reduced further by generalising the argument used by Sprague. First observe that any shape of diameter one can be contained inside a curve of constant width one (such as a cirle of unit diameter, or a Reuleaux polygon) so to prove that a set of points is a universal cover it suffices to show that it can cover a set congruent to every curve of constant width one. When such a curve is fitted inside the hexagon it will touch each of the six sides of the hexagon at a unique point. On the side running from D to C it must be to the left of the point P on the corner of the removed triangle C. This means that all points near A outside an arc of radius one centred on P can be removed. Similarly the curve must touch the edge of the hexagon from E to D somewhere right of N, the corner of the triangle E that has been removed. So all points outside an arc of radius one centred on N can also be removed. The remaining cover then has a vertex at X where these two arcs meet. This reduces the cover but not enough to make it smaller for any non-zero value of $\sigma$ than Sprague's universal cover which is the case $\sigma=0$.

enter image description here

One more piece can be removed if we use the freedom to reflect shapes. The axis of reflection to use is the line from the midpoint M of the side of the hexagon from E to D, to the midpoint of the opposite side. A shape fitted into the hexagon with the corners E and C removed can be reflected about this axis provided it also does not enter the triangles F' and D' which are the reflections of C and E about the axis. When this is the case we will choose to reflect the shape if it touches the side from E to D at a point nearer to E than D. Remember that it touches the opposite side at the opposite point which is therefore also reflected to be nearer the corner of the hexagon at B than the one at A. If we draw an arc centred on M of radius one it cuts off a larger region near A and no shape that can be reflected can be beyond this line. The point where this meets the arc centred on P is marked W.

enter image description here

This means that the only shapes that can have points outside that arc are ones that cannot be reflected. This means they must enter some point inside the regions F' or D' If they have a point in D' then they cannot have a point in A' which is the triangle whose points are at a distance of more than one from all points in D'. Draw one more arc centred on Q at the corner of the traingle C' which is the reflection of the region F. All points in C' are at a distance of one or more than one from points in F' so the arc will touch the region F' but not enter it. This arc will meet the arc centred on M at a point Z and the arc centred on N at a point Y. Now consider the fate of points inside the region XYZW bounded by the four arcs. It is a general property of curves of constant width one that if two points are inside the curve then all points on an arc of radius one through the two points are also inside the curve. Suppose then that a shape fitted inside the hexagon had a point in XYZW and also in F' We could then join those two points with an arc but between the two points it would be outside the arc centered on Q and would therefore go outside the hexagon. This is in contradiction with the premise so we conclude that no shape fitted in the hexagon can have a point in both XYZW and F'. It can also be verified that for angles $\sigma$ less than 9 degrees the region XYZW is inside the triangle A'. Therefore shapes with a point insode XYZW do not have points in F' or D' and can be reflected. However, we have already determined that such shapes will not have points in this region. This proves that the region XYZW can be removed from the universal cover.

It turns out that this is now sufficient to construct a universal cover smaller than the ones of Hansen and Duff. Even if we restrict ouselves to the convex case and remove only the part of this region that leaves a convex shape, the area of the universal cover for an angle $\sigma = 0.4$ degrees can be computed to be 0.8441177

There are other small pieces that can be removed from this cover to reduce it further.

This of course does not solve Lebesgue's Universal Covering Problem which is hard because of the complexity of the problem (not because the numbers involved are irrational as asked in the question) However I can break the problem down with three conjectures

1st conjecture: The minimal convex cover for any subset of curves of width one will always fit inside a hexagon circumscribed around a circle such that opposite sides are parallel. It can be shown that such a shape is a universal cover but only computational evidence supports the truth of this conjecture.

2nd conjecture: For any such hexagon there is a minimal convex cover. The conjecture is that the minimum area for such a cover is found for the case of the regular hexagon. Again computation supports this conjecture.

3rd conjecture: For a regular hexagon the minimum cover within the hexagon for any subset of curves of width one fits inside the shape formed by removing two corners by two lines tangent to the inscribed circle and at an angle of 60 degrees to each other (as above)

If all of these three conjectures are true then the problem of finding the minimal convex cover reduces to finding the minimal cover inside a shape of this form. The conjectures may be hard to prove but if are true then the final problem may be tractable using methods similar to the above proof.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.