Généraliser le problème de Borsuk: dans quelle mesure peut-on rétrécir un ensemble planaire de diamètre 1 en le coupant en $k$ pièces?
Le problème de Borsuk demande si un ensemble borné$\mathbb{R}^n$ peut être divisé en $n+1$ensembles de diamètre strictement plus petit. Bien que vrai quand$n=1,2,3$, ça échoue en dimension $64$et plus haut; Je crois tous les autres$n$ sont ouverts au moment de la rédaction de cet article.
Cependant, il s'avère qu'au moins dans le $n=2$cas on peut être plus précis que "diamètre strictement plus petit"; si l'ensemble d'origine a un diamètre de 1, nous pouvons nous assurer que chaque pièce a un diamètre au plus$\frac{\sqrt{3}}{2}\approx 0.866$, une limite atteinte par le cercle de diamètre $1$. Pour voir que cela tient, nous notons que l'hexagone régulier de largeur$1$est une solution au problème de recouvrement universel de Lebesgue , et peut être divisé en trois ensembles de diamètre$\frac{\sqrt{3}}2$aussi:
En utilisant la même approche que ci-dessus (trouver des ensembles spécifiques avec une limite inférieure et disséquer une couverture universelle pour des ensembles de diamètre 1), j'ai quelques limites pour $k$ aussi bien, mais seulement pour $k=3,4,7$ sont-ils exacts:
(Extension de ce tableau au-delà $k=7$ serait difficile, car l'élaboration de dissections optimales pour le cercle deviendrait beaucoup plus compliquée.)
Edit: En prenant des discours à$72^\circ$ angles sur un hexagone régulier (avec un rayon rencontrant l'hexagone au milieu d'un côté), je pense que je peux obtenir une limite supérieure légèrement meilleure d'environ $0.6434$ pour le cas $k=5$. Optimiser davantage le placement des rayons (afin que les distances entre les extrémités des rayons soient égales) me permet de me déplacer$0.6223$.
Dans la limite, je pense que le diamètre de chaque pièce est asymptotique pour $\sqrt{\frac{2\pi}{3\sqrt{3}k}}\approx \frac{1.1}{\sqrt{k}}$par carrelage avec des hexagones réguliers. On ne peut certainement pas faire mieux que$1/\sqrt{k}$lors de la division du cercle, en utilisant l'inégalité isodiamétrique (si les pièces étaient plus petites, elles auraient trop peu de surface). En utilisant une dissection triviale du carré, on a également une limite supérieure de$\frac{\sqrt{2}}{\lceil\sqrt{k}\rceil}$.
Quelques questions que j'ai sur ce problème:
Cette question a-t-elle déjà été étudiée dans la littérature? Si oui, que sait-on?
Y a-t-il $k$ pour lequel le cercle ne présente pas le pire scénario de dissection?
Le $k=5,6$les limites supérieures sont-elles sensiblement améliorées? Je pense que l'utilisation de la solution légèrement plus petite de Pal au problème de la couverture universelle permettrait quelques ajustements lorsque$k=6$, mais je n'ai pas travaillé sur les détails.
Réponses
quel est le diamètre minimum que l'on peut garantir lors de la découpe d'un ensemble plan de diamètre unitaire en $k$ pièces?
Ce problème est considéré en 1974 dans le problème 102 de [SCY], où le diamètre minimum est noté $\delta_2(k)$. Malheureusement, il n'y a pas beaucoup plus de limites que dans votre question. Un outil principal pour l'évaluation$\delta_2(k)$ il y a $\delta(k, A)$, le diamètre minimum que l'on peut garantir lors de la découpe d'un ensemble plan $A$ de diamètre unitaire en $k$pièces. Spécial pour$S$ les boîtiers sont-ils un disque $D$, un carré $S$, et un triangle équilatéral $T$. Dans Problèmes 103 et tableau à la p. 97 (référencé au papier [Gra] de 1967)$\delta(k, A)$ sont affichés pour $D$ pour $k\le 5$, pour $T$ et $k\le 10$, et pour $S$ et $k\le 4$. Également dans [Gra] sont évalués$\delta(k, T)$ pour $k\le 15$. Quand j'étais écolier, en 1991 j'ai lu l'article [KK] où étaient calculés$\delta(2,S)=\tfrac {\sqrt{10}}4$, $\delta(3,S)=\tfrac {\sqrt{130}}{16}=0.712\dots$, et $\delta(5,S)=\tfrac {5\sqrt{34}}{64}=0.455\dots$, a trouvé une limite supérieure $0.4200\dots$ sur $\delta(6, S)$, et a noté que $\delta(k, D)$ pour $k\ge 8$ et $\delta(k,T)$ pour $k\ge 16$sont inconnus. Aux pages 96 et 98 sont écrites des pensées plutôt pessimistes sur cette approche et dans le problème 104 sont indiquées des valeurs$\delta_2(2)$, $\delta_2(3)$, $\delta_2(4)$, et $\delta_2(7)$, que vous connaissez déjà. Il est à noter qu'aucune autre valeur exacte pour$\delta_2(k)$ quand $k\ge 2$sont connus. Valeur de$\delta_2(3)$, a été, en fait, trouvé par Borsuk [Bor1, Bor2] en 1932–1933 (voir aussi [Gal]). En 1956, un géomètre allemand Lenz [Len1, Len2] a étudié à fond les valeurs de$\delta_2(k)$ pour petit $k$ et calculé $\delta_2(4)$, $\delta_2(5)$ et $\delta_2(7)$. Valeur de$\delta_2(4)$a également été trouvé par Selfridge [Sel]. Dans [Gru] on observe que si$G_{11}$ est un habitué $11$-gon de diamètre $1$ puis $\delta_2(6)\ge \delta(6, G_{11})=\frac 1{2\cos (\pi/22)}=0.505141\dots$.
Malheureusement, je ne parle pas allemand, mais je suppose que dans [Len1] à la p. 34 sont des limites fournies$\delta_2(k)\le\tfrac {\sqrt{2}}{\lfloor \sqrt{k}\rfloor}$ pour $k\ge 2$ et $\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$ pour $k\ge 5$, et à la p. 36 un bond$\delta_2(k)\le\tfrac 1{k-1}\left(\tfrac {2}{\sqrt{3}}+\sqrt{\tfrac 43+ \frac{2\pi}{\sqrt{27}}(k-1) }\right)$. Les deux dernières limites concernent$\sqrt{\frac{2\pi}{\sqrt{27}}}k^{-1/2}\approx 1.1 k^{-1/2}$.
Mais ces références sont anciennes et des progrès pourraient être réalisés à partir de cette époque.
On devrait avoir $\delta_2(k)\approx \sqrt{\frac{2\pi}{\sqrt{27}}}k^{-1/2}$ asymptotiquement, voir ci-dessous.
Une borne inférieure. Donné$k$, Le principe de Pigeonhole implique $\delta_2(k)\ge d(k+1)/2$, où $d(k+1)$ être une distance minimale maximale possible entre $k+1$points du disque de l'unité, voir ce fil. Cette approche devrait fournir une borne asymptotique$\delta_2(k)\ge\approx \sqrt{\tfrac {2\pi}{3\sqrt{3}k}}\approx 1.1 k^{-1/2}$.
Une borne supérieure. Laisser$C$ a être un sous-ensemble (pas nécessairement convexe) du plan qui contient une copie congruente de chaque ensemble planaire de diamètre unitaire et $a$ être un domaine de $S$. Les limites les plus connues pour$a$ sont à propos de $0.8441$, voir un fil sur une quête difficile et ingrate pour eux. Si$C$ peut être couvert par $k$ cellules d'une grille hexagonale avec côté $d$ puis $\delta_2(k)\le 2d$. Cette approche devrait fournir une borne asymptotique$\delta_2(k)\le\approx 2\sqrt{\tfrac {2a}{3\sqrt{3}k}}\approx 1.14 k^{-1/2}$.
Mais la borne de Lenz suggère que nous n'avons pas besoin d'utiliser un ensemble de recouvrement universel, car à la page 11 de [Lit], il est montré qu '«une aire de (plus grand) diamètre ne dépasse pas $1$ est au plus $\tfrac{\pi}4$».
Cette observation devrait indiquer une limite supérieure asymptotiquement serrée.
Les références
[Bor1] K. Borsuk, Über die Zerlegung einer euklidischen$n$-dimensionalen Vollkugel dans $n$Mengen , Verhandlungen Stagiaire. Math. Kongr., Zurich 2 (1932) 192.
[Bor2] K. Borsuk, Drei Sätze über meurent$n$-Späre dimensionnel , Fundamenta Math. 20 (1933), 177-190.
[Gal] D. Gale, sur l'inscription$n$-ensembles dimensionnels est un régulier $n$-simplex , Proc. Amer. Math. Soc. 4 (1953) 222-225.
[Gra] RL Graham, Sur les partitions d'un triangle équilatéral , Canadian Journ. Math. 19 (1967) 394–409.
[Gru] B. Grünbaum, Etudes en géométrie combinatoire et théorie des corps convexes , Moskow, Nauka, 1971, en russe.
[KK] I. Kokorev, L. Kurlyandchik, Un gros gâteau sur de petites assiettes , 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] JE Littelwood, A Mathematician's Miscellany , Methued & Co, Londres, publié pour la première fois en 1953.
[SCY] DO Shklyarskiy, NN Chentsov, IM Yaglom, Estimations géométriques et problèmes de géométrie combinatoire , Moskow, Nauka, 1974, en russe.
[Sel] JL Selfridge, Un séminaire informel sur les revêtements des ensembles convexes (Rapport de l 'Inst. Dans la Théorie des Nombres), Colorado, 1959. 334.