Verallgemeinerung des Borsuk-Problems: Um wie viel können wir einen planaren Satz mit Durchmesser 1 verkleinern, indem wir ihn einschneiden? $k$ Stücke?
Borsuks Problem fragt, ob ein begrenzter Satz einsetzt$\mathbb{R}^n$ kann aufgeteilt werden in $n+1$Sätze mit streng kleinerem Durchmesser. Während wahr wann$n=1,2,3$, es versagt in der Dimension $64$und höher; Ich glaube allen anderen$n$ sind zum jetzigen Zeitpunkt offen.
Es stellt sich jedoch heraus, dass zumindest in der $n=2$Fall können wir genauer sein als "streng kleinerer Durchmesser"; Wenn der ursprüngliche Satz Durchmesser 1 hat, können wir sicherstellen, dass jedes Stück höchstens einen Durchmesser hat$\frac{\sqrt{3}}{2}\approx 0.866$eine Grenze, die durch den Kreis des Durchmessers erreicht wird $1$. Um zu sehen, dass dies gilt, stellen wir fest, dass das reguläre Sechseck der Breite$1$ist eine Lösung für das universelle Abdeckungsproblem von Lebesgue und kann in drei Durchmessersätze unterteilt werden$\frac{\sqrt{3}}2$auch:
Unter Verwendung des gleichen Ansatzes wie oben (Finden bestimmter Sätze mit einer unteren Grenze und Zerlegen einer universellen Abdeckung für Sätze mit Durchmesser 1) habe ich einige Grenzen für höhere $k$ auch, wenn auch nur für $k=3,4,7$ sind sie genau:
(Erweitern Sie diese Tabelle darüber hinaus $k=7$ wäre schwierig, da die Erarbeitung optimaler Präparationen für den Kreis viel komplizierter würde.)
Edit: Durch Speichen nehmen bei$72^\circ$ Winkel auf einem regulären Sechseck (wobei eine Speiche auf das Sechseck in der Mitte einer Seite trifft), denke ich, dass ich eine etwas bessere Obergrenze von herum erhalten kann $0.6434$ Im Falle $k=5$. Durch eine weitere Optimierung der Speichenplatzierung (sodass die Abstände zwischen den Speichenendpunkten gleich sind) komme ich herum$0.6223$.
Im Limit denke ich, dass der Durchmesser jedes Stückes asymptotisch ist $\sqrt{\frac{2\pi}{3\sqrt{3}k}}\approx \frac{1.1}{\sqrt{k}}$durch Kacheln mit regelmäßigen Sechsecken. Sicher kann man es nicht besser machen als$1/\sqrt{k}$Beim Teilen des Kreises unter Verwendung der isodiametrischen Ungleichung (wenn die Teile kleiner wären, hätten sie zu wenig Fläche). Unter Verwendung einer trivialen Dissektion des Quadrats hat man auch eine Obergrenze von$\frac{\sqrt{2}}{\lceil\sqrt{k}\rceil}$.
Einige Fragen zu diesem Problem:
Wurde diese Frage bereits in der Literatur untersucht? Wenn ja, was ist bekannt?
Sind da welche $k$ für die der Kreis nicht das Worst-Case-Szenario für die Dissektion darstellt?
Kann der $k=5,6$Obergrenzen wesentlich verbessert werden? Ich denke, die Verwendung der etwas kleineren Lösung von Pal für das Problem der universellen Abdeckung würde einige Anpassungen ermöglichen, wenn$k=6$, habe aber die Details nicht ausgearbeitet.
Antworten
Was ist der Mindestdurchmesser, den man beim Schneiden eines planaren Satzes von Einheitsdurchmessern sicherstellen kann? $k$ Stücke?
Dieses Problem wird 1974 in Problem 102 von [SCY] betrachtet, wo der minimale Durchmesser angegeben ist $\delta_2(k)$. Leider gibt es nicht viel mehr Grenzen als in Ihrer Frage. Ein Hauptwerkzeug für die Bewertung von$\delta_2(k)$ es gibt $\delta(k, A)$ist der minimale Durchmesser, den man beim Schneiden eines planaren Satzes sicherstellen kann $A$ des Einheitsdurchmessers in $k$Stücke. Besonderes für$S$ In diesen Fällen handelt es sich um eine Festplatte $D$, ein Quadrat $S$und ein gleichseitiges Dreieck $T$. In Aufgabe 103 und Tabelle auf S. 97 (bezogen auf Papier [Gra] von 1967) Grenzen$\delta(k, A)$ werden angezeigt für $D$ zum $k\le 5$, zum $T$ und $k\le 10$, und für $S$ und $k\le 4$. Auch in [Gra] werden ausgewertet$\delta(k, T)$ zum $k\le 15$. Als ich ein Schüler war, las ich 1991 den Artikel [KK], in dem berechnet wurde$\delta(2,S)=\tfrac {\sqrt{10}}4$, $\delta(3,S)=\tfrac {\sqrt{130}}{16}=0.712\dots$, und $\delta(5,S)=\tfrac {5\sqrt{34}}{64}=0.455\dots$fand eine Obergrenze $0.4200\dots$ auf $\delta(6, S)$und stellte fest, dass $\delta(k, D)$ zum $k\ge 8$ und $\delta(k,T)$ zum $k\ge 16$sind unbekannt. Auf den Seiten 96 und 98 sind eher pessimistische Gedanken zu diesem Ansatz geschrieben und in Aufgabe 104 sind Werte dargestellt$\delta_2(2)$, $\delta_2(3)$, $\delta_2(4)$, und $\delta_2(7)$, die du schon kennst. Es wird darauf hingewiesen, dass keine anderen genauen Werte für$\delta_2(k)$ wann $k\ge 2$sind bekannt. Wert von$\delta_2(3)$wurde tatsächlich von Borsuk [Bor1, Bor2] in den Jahren 1932–1933 gefunden (siehe auch [Gal]). 1956 untersuchte ein deutscher Geometer Lenz [Len1, Len2] gründlich die Werte von$\delta_2(k)$ für kleine $k$ und berechnet $\delta_2(4)$, $\delta_2(5)$ und $\delta_2(7)$. Wert von$\delta_2(4)$wurde auch von Selfridge [Sel] gefunden. In [Gru] wird beobachtet, dass wenn$G_{11}$ ist eine regelmäßige $11$-gon des Durchmessers $1$ dann $\delta_2(6)\ge \delta(6, G_{11})=\frac 1{2\cos (\pi/22)}=0.505141\dots$.
Leider spreche ich kein Deutsch, aber ich denke, dass in [Len1] auf S. 34 sind Grenzen vorgesehen$\delta_2(k)\le\tfrac {\sqrt{2}}{\lfloor \sqrt{k}\rfloor}$ zum $k\ge 2$ und $\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$ zum $k\ge 5$und auf p. 36 eine Grenze$\delta_2(k)\le\tfrac 1{k-1}\left(\tfrac {2}{\sqrt{3}}+\sqrt{\tfrac 43+ \frac{2\pi}{\sqrt{27}}(k-1) }\right)$. Beide letzteren Grenzen sind ungefähr$\sqrt{\frac{2\pi}{\sqrt{27}}}k^{-1/2}\approx 1.1 k^{-1/2}$.
Diese Referenzen sind jedoch alt und aus dieser Zeit könnten einige Fortschritte erzielt werden.
Wir hätten sollen $\delta_2(k)\approx \sqrt{\frac{2\pi}{\sqrt{27}}}k^{-1/2}$ asymptotisch, siehe unten.
Eine Untergrenze. Gegeben$k$, Taubenlochprinzip impliziert $\delta_2(k)\ge d(k+1)/2$, wo $d(k+1)$ ein maximal möglicher Mindestabstand zwischen sein $k+1$Punkte der Einheitsscheibe, siehe diesen Thread. Dieser Ansatz sollte eine asymptotische Bindung liefern$\delta_2(k)\ge\approx \sqrt{\tfrac {2\pi}{3\sqrt{3}k}}\approx 1.1 k^{-1/2}$.
Eine Obergrenze. Lassen$C$ a sei eine (nicht unbedingt konvexe) Teilmenge der Ebene, die eine kongruente Kopie jeder planaren Menge von Einheitsdurchmesser und enthält $a$ ein Bereich von sein $S$. Die bekanntesten Grenzen für$a$ sind über $0.8441$, siehe einen Thread über eine harte und undankbare Suche nach ihnen. Wenn$C$ kann abgedeckt werden durch $k$ Zellen eines sechseckigen Gitters mit Seite $d$ dann $\delta_2(k)\le 2d$. Dieser Ansatz sollte eine asymptotische Bindung liefern$\delta_2(k)\le\approx 2\sqrt{\tfrac {2a}{3\sqrt{3}k}}\approx 1.14 k^{-1/2}$.
Aber Lenz 'Bindung legt nahe, dass wir kein universelles Abdeckungsset verwenden müssen, weil auf S.11 von [Lit] gezeigt wird, dass „eine Fläche mit (größtem) Durchmesser nicht größer als ist $1$ ist höchstens $\tfrac{\pi}4$”.
Diese Beobachtung sollte auf eine asymptotisch enge Obergrenze hinweisen.
Verweise
[Bor1] K. Borsuk, Über die Zerlegung einer euklidischen$n$-dimensionalen Vollkugel in $n$Mengen , Verhandlungen Intern. Mathematik. Kongr., Zürich 2 (1932) 192.
[Bor2] K. Borsuk, Drei Sätze über sterben$n$-dimensionale Späre , Fundamenta Math. 20 (1933), 177–190.
[Gal] D. Gale, Über das Einschreiben$n$-dimensionale Mengen ist eine reguläre $n$-simplex , Proc. Amer. Mathematik. Soc. 4 (1953) 222–225.
[Gra] RL Graham, Auf Trennwänden eines gleichseitigen Dreiecks , Canadian Journ. Mathematik. 19 (1967) 394–409.
[Gru] B. Grünbaum, Etüden in kombinatorischer Geometrie und Theorie konvexer Körper , Moskau, Nauka, 1971, in russischer Sprache.
[KK] I. Kokorev, L. Kurlyandchik, Ein großer Kuchen auf kleinen Tellern , Kvant 7 (1991) 13–17.
[Len1] H. Lenz, Über die Bedeckung ebener Punktmengen durch staatliche Rechte Durchmessers , Archiv Math. 7 (1956) 34–40, doi: 10.1007 / bf01900521.
[Len2] H. Lenz, Zerlegung ebener Schritte in konvexen Zellen von möglichst kleinem Durchmessers , Jahresber. Deutsch. Mathematik. Vereinigung 58 (1956) 87–97.
[Lit] JE Littelwood, Verschiedenes eines Mathematikers , Methued & Co, London, erstmals 1953 veröffentlicht.
[SCY] DO Shklyarskiy, NN Chentsov, IM Yaglom, Geometrische Schätzungen und kombinatorische Geometrieprobleme , Moskau, Nauka, 1974, in russischer Sprache.
[Sel] JL Selfridge, Ein informelles Seminar über die Abdeckung konvexer Mengen (Bericht des Instituts für Zahlentheorie), Colorado, 1959. 334.