Borsuk's problem asks whether a bounded set in $\mathbb{R}^n$ can be split into $n+1$ sets of strictly smaller diameter. While true when $n=1,2,3$, it fails in dimension $64$ and higher; I believe all other $n$ are open as of this writing.
However, it turns out that at least in the $n=2$ case we can be more precise than "strictly smaller diameter"; if the original set has diameter 1, we can ensure that each piece has diameter at most $\frac{\sqrt{3}}{2}\approx 0.866$, a bound attained by the circle of diameter $1$. To see that this holds, we note that the regular hexagon of width $1$ is a solution to Lebesgue's universal covering problem, and can be split into three sets of diameter $\frac{\sqrt{3}}2$ as well:
I am interested in putting bounds on such dissections with more than $3$ pieces: what is the minimum diameter one can ensure when cutting a planar set of unit diameter into $k$ pieces?
Using the same approach as above (finding specific sets with a lower bound, and dissecting a universal cover for sets of diameter 1), I have some bounds for higher $k$ as well, though only for $k=3,4,7$ are they exact:
(Extending this table beyond $k=7$ would be difficult, as working out optimal dissections for the circle would become much more complicated.)
Edit: By taking spokes at $72^\circ$ angles on a regular hexagon (with one spoke meeting the hexagon at the midpoint of a side), I think I can get a slightly better upper bound of around $0.6434$ for the case $k=5$. Optimizing spoke placement further (so that the distances between spoke endpoints are equal) gets me around $0.6223$.
In the limit, I think the diameter of each piece is asymptotic to $\sqrt{\frac{2\pi}{3\sqrt{3}k}}\approx \frac{1.1}{\sqrt{k}}$ by tiling with regular hexagons. Certainly one can do no better than $1/\sqrt{k}$ when dividing the circle, using the isodiametric inequality (if the pieces were any smaller, they would have too little area). Using a trivial dissection of the square, one also has an upper bound of $\frac{\sqrt{2}}{\lceil\sqrt{k}\rceil}$.
Some questions I have about this problem:
-
Has this question been investigated before in the literature? If so, what is known?
-
Are there any $k$ for which the circle does not present the worst-case scenario for dissection?
-
Can the $k=5,6$ upper bounds be substantially improved? I think using Pal's slightly smaller solution to the universal covering problem would allow for a few adjustments when $k=6$, but haven't worked out the details.
Best Answer
This problem is considered in 1974 in Problem 102 from [SCY], where the minimum diameter is denoted $\delta_2(k)$. Unfortunately, there are given not much more bounds than in your question. A main tool for the evaluation of $\delta_2(k)$ there is $\delta(k, A)$, the minimum diameter one can ensure when cutting a planar set $A$ of unit diameter into $k$ pieces. Special for $S$ are cases are a disk $D$, a square $S$, and an equilateral triangle $T$. In Problems 103 and table at p. 97 (referenced to paper [Gra] from 1967) bounds $\delta(k, A)$ are shown for $D$ for $k\le 5$, for $T$ and $k\le 10$, and for $S$ and $k\le 4$. Also in [Gra] are evaluated $\delta(k, T)$ for $k\le 15$. When I was a schoolboy, in 1991 I read the article [KK] where were calculated $\delta(2,S)=\tfrac {\sqrt{10}}4$, $\delta(3,S)=\tfrac {\sqrt{130}}{16}=0.712\dots$, and $\delta(5,S)=\tfrac {5\sqrt{34}}{64}=0.455\dots$, found an upper bound $0.4200\dots$ on $\delta(6, S)$, and noted that $\delta(k, D)$ for $k\ge 8$ and $\delta(k,T)$ for $k\ge 16$ are unknown. At pages 96 and 98 are written rather pessimistic thoughts about this approach and in Problem 104 are shown values $\delta_2(2)$, $\delta_2(3)$, $\delta_2(4)$, and $\delta_2(7)$, which you already know. There is noted that no other exact values for $\delta_2(k)$ when $k\ge 2$ are known. Value of $\delta_2(3)$, was, in fact, found by Borsuk [Bor1, Bor2] in 1932–1933 (see also [Gal]). In 1956 a German geometer Lenz [Len1, Len2] thoroughly studied values of $\delta_2(k)$ for small $k$ and calculated $\delta_2(4)$, $\delta_2(5)$ and $\delta_2(7)$. Value of $\delta_2(4)$ was found also by Selfridge [Sel]. In [Gru] is observed that if $G_{11}$ is a regular $11$-gon of diameter $1$ then $\delta_2(6)\ge \delta(6, G_{11})=\frac 1{2\cos (\pi/22)}=0.505141\dots$.
Unfortunately, I don’t speak German, but I guess that in [Len1] at p. 34 are provided bounds $\delta_2(k)\le\tfrac {\sqrt{2}}{\lfloor \sqrt{k}\rfloor}$ for $k\ge 2$ and $\delta_2(k)<\tfrac 1{k-8\pi/\sqrt{27}}\left\lfloor\tfrac {4\pi}{\sqrt{27}}+\sqrt{\tfrac{2\pi k}{\sqrt{27}} }\right\rfloor$ for $k\ge 5$, and at p. 36 a bound $\delta_2(k)\le\tfrac 1{k-1}\left(\tfrac {2}{\sqrt{3}}+\sqrt{\tfrac 43+ \frac{2\pi}{\sqrt{27}}(k-1) }\right)$. Both latter bounds are about $\sqrt{\frac{2\pi}{\sqrt{27}}}k^{-1/2}\approx 1.1 k^{-1/2}$.
But these references are old and some progress could be made from that time.
We should have $\delta_2(k)\approx \sqrt{\frac{2\pi}{\sqrt{27}}}k^{-1/2}$ asymptotically, see below.
A lower bound. Given $k$, Pigeonhole principle implies $\delta_2(k)\ge d(k+1)/2$, where $d(k+1)$ be a maximal possible minimum distance between $k+1$ points of the unit disk, see this thread. This approach should provide an asymptotic bound $\delta_2(k)\ge\approx \sqrt{\tfrac {2\pi}{3\sqrt{3}k}}\approx 1.1 k^{-1/2}$.
An upper bound. Let $C$ a be a (not necessarily convex) subset of the plane that contains a congruent copy of every planar set of unit diameter and $a$ be an area of $S$. The best known bounds for $a$ are about $0.8441$, see a thread about a hard and ungrateful quest for them. If $C$ can be covered by $k$ cells of a hexagonal grid with side $d$ then $\delta_2(k)\le 2d$. This approach should provide an asymptotic bound $\delta_2(k)\le\approx 2\sqrt{\tfrac {2a}{3\sqrt{3}k}}\approx 1.14 k^{-1/2}$.
But Lenz’ bound suggest that we don’t need to use an universal covering set, because at p.11 of [Lit] it is shown that “an area of (greatest) diameter not greater than $1$ is at most $\tfrac{\pi}4$”.
This observation should point to an asymptotically tight upper bound.
References
[Bor1] K. Borsuk, Über die Zerlegung einer euklidischen $n$-dimensionalen Vollkugel in $n$ Mengen, Verhandlungen Intern. Math. Kongr., Zürich 2 (1932) 192.
[Bor2] K. Borsuk, Drei Sätze über die $n$-dimensional Späre, Fundamenta Math. 20 (1933), 177–190.
[Gal] D. Gale, On inscribing $n$-dimensional sets is a regular $n$-simplex, Proc. Amer. Math. Soc. 4 (1953) 222–225.
[Gra] R.L. Graham, On partitions of a equilateral triangle, Canadian Journ. Math. 19 (1967) 394–409.
[Gru] B. Grünbaum, Etudes in combinatorial geometry and the theory of convex bodies, Moskow, Nauka, 1971, in Russian.
[KK] I. Kokorev, L. Kurlyandchik, A big cake on small plates, Kvant 7 (1991) 13–17.
[Len1] H. Lenz, Über die Bedeckung ebener Punktmengen durch solche kleineren Durchmessers, Archiv Math. 7 (1956) 34–40, doi:10.1007/bf01900521.
[Len2] H. Lenz, Zerlegung ebener Bereiche in konvexe Zellen von möglichst kleinem Durchmessers, Jahresber. Deutsch. Math. Vereinigung 58 (1956) 87–97.
[Lit] J.E. Littelwood, A Mathematician’s Miscellany, Methued & Co, London, first published in 1953.
[SCY] D.O. Shklyarskiy, N.N. Chentsov, I.M. Yaglom, Geometrical estimations and combinatorial geometry problems, Moskow, Nauka, 1974, in Russian.
[Sel] J.L. Selfridge, An informal seminar on the coverings of convex sets (Report of the Inst. in the Theory of Numbers), Colorado, 1959. 334.