Uogólniając problem Borsuka: o ile możemy zmniejszyć planarny zbiór o średnicy 1, wycinając go $k$ kawałki?

Question

Problem Borsuka dotyczy tego, czy zestaw ograniczony$\mathbb{R}^n$ można podzielić na $n+1$zestawy o ściśle mniejszej średnicy. Chociaż prawda, kiedy$n=1,2,3$, zawodzi w wymiarze $64$i wyżej; Wierzę wszystkim innym$n$ są otwarte w chwili pisania tego tekstu.

Okazuje się jednak, że przynajmniej w $n=2$przypadku możemy być bardziej precyzyjni niż „ściśle mniejsza średnica”; jeśli oryginalny zestaw ma średnicę 1, możemy zapewnić, że każdy element ma co najwyżej średnicę$\frac{\sqrt{3}}{2}\approx 0.866$, ograniczenie osiągnięte przez koło średnicy $1$. Aby zobaczyć, że tak jest, zauważamy, że regularny sześciokąt o szerokości$1$jest rozwiązaniem uniwersalnego problemu pokrycia Lebesgue'a i można go podzielić na trzy zestawy średnic$\frac{\sqrt{3}}2$również:

jestem zainteresowany ograniczaniem takich sekcji z więcej niż$3$ sztuk: jaka jest minimalna średnica, jaką można zapewnić podczas cięcia płaskiego zestawu średnic jednostkowych na $k$ kawałki?

Stosując to samo podejście co powyżej (znajdowanie określonych zestawów z dolną granicą i wycinanie uniwersalnej osłony dla zestawów o średnicy 1), mam pewne ograniczenia dla wyższych $k$ również, choć tylko dla $k=3,4,7$ czy są dokładne:

(Poszerzenie tabeli poza $k=7$ byłoby trudne, ponieważ wypracowanie optymalnych sekcji dla koła stałoby się znacznie bardziej skomplikowane).

Edycja: biorąc szprychy o godz$72^\circ$ kąty na regularnym sześciokącie (z jedną szprychą stykającą się z sześciokątem w środku boku), myślę, że mogę uzyskać nieco lepszą górną granicę wokół $0.6434$ w przypadku $k=5$. Dalsza optymalizacja rozmieszczenia szprych (tak, aby odległości między punktami końcowymi szprych były równe) pozwala mi się obejść$0.6223$.

W granicach, myślę, że średnica każdego kawałka jest asymptotyczna $\sqrt{\frac{2\pi}{3\sqrt{3}k}}\approx \frac{1.1}{\sqrt{k}}$poprzez układanie płytek regularnymi sześciokątami. Z pewnością nie można zrobić nic lepszego niż$1/\sqrt{k}$podczas dzielenia koła za pomocą nierówności izodiametrycznej (gdyby kawałki były mniejsze, miałyby za mało pola). Używając trywialnego podziału kwadratu, uzyskuje się również górną granicę$\frac{\sqrt{2}}{\lceil\sqrt{k}\rceil}$.

Kilka pytań dotyczących tego problemu:

• Czy to pytanie było już badane w literaturze? Jeśli tak, co wiadomo?

• Czy są jakieś $k$ dla których koło nie przedstawia najgorszego scenariusza dla sekcji?

• Czy $k=5,6$górne granice ulegną znacznej poprawie? Myślę, że użycie nieco mniejszego rozwiązania Pala do problemu uniwersalnego pokrycia pozwoliłoby na kilka poprawek, kiedy$k=6$, ale nie dopracowałem szczegółów.

Answer 1

jaka jest minimalna średnica, jaką można zapewnić podczas wycinania płaskiego zestawu średnicy jednostkowej $k$ kawałki?

Zagadnieniem tym zajmuję się w 1974 roku w Problemie 102 z [SCY], gdzie zaznaczono minimalną średnicę $\delta_2(k)$. Niestety nie podano dużo więcej ograniczeń niż w Twoim pytaniu. Główne narzędzie do oceny$\delta_2(k)$ jest $\delta(k, A)$minimalną średnicę, jaką można zapewnić przy wycinaniu płaskiego zestawu $A$ średnicy jednostki do $k$sztuk. Specjalnie dla$S$ czy skrzynie są dyskiem $D$, plac $S$i trójkąt równoboczny $T$. W zadaniach 103 i tabeli na str. 97 (w odniesieniu do papieru [Gra] z 1967 r.)$\delta(k, A)$ są wyświetlane dla $D$ dla $k\le 5$, dla $T$ i $k\le 10$, i dla $S$ i $k\le 4$. Również w [Gra] są oceniane$\delta(k, T)$ dla $k\le 15$. Kiedy byłem uczniem, w 1991 roku przeczytałem artykuł [KK], w którym obliczono$\delta(2,S)=\tfrac {\sqrt{10}}4$, $\delta(3,S)=\tfrac {\sqrt{130}}{16}=0.712\dots$, i $\delta(5,S)=\tfrac {5\sqrt{34}}{64}=0.455\dots$, znalazła górną granicę $0.4200\dots$ na $\delta(6, S)$i zauważyłem, że $\delta(k, D)$ dla $k\ge 8$ i $\delta(k,T)$ dla $k\ge 16$są nieznane. Na stronach 96 i 98 są napisane raczej pesymistyczne przemyślenia na temat tego podejścia, aw Problemie 104 przedstawiono wartości$\delta_2(2)$, $\delta_2(3)$, $\delta_2(4)$, i $\delta_2(7)$które już znasz. Należy zauważyć, że nie ma innych dokładnych wartości dla$\delta_2(k)$ kiedy $k\ge 2$są znane. Wartość$\delta_2(3)$, faktycznie został znaleziony przez Borsuka [Bor1, Bor2] w latach 1932–1933 (patrz także [Gal]). W 1956 roku niemiecki geometr Lenz [Len1, Len2] dokładnie zbadał wartości$\delta_2(k)$ za małe $k$ i obliczone $\delta_2(4)$, $\delta_2(5)$ i $\delta_2(7)$. Wartość$\delta_2(4)$został również znaleziony przez Selfridge [Sel]. W [Gru] obserwuje się, że jeśli$G_{11}$ jest regularny $11$-gon średnicy $1$ następnie $\delta_2(6)\ge \delta(6, G_{11})=\frac 1{2\cos (\pi/22)}=0.505141\dots$.

Niestety nie mówię po niemiecku, ale myślę, że w [Len1] na str. 34 są wyznaczone granice$\delta_2(k)\le\tfrac {\sqrt{2}}{\lfloor \sqrt{k}\rfloor}$ dla $k\ge 2$ i $\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$ dla $k\ge 5$i na str. 36 skrępowany$\delta_2(k)\le\tfrac 1{k-1}\left(\tfrac {2}{\sqrt{3}}+\sqrt{\tfrac 43+ \frac{2\pi}{\sqrt{27}}(k-1) }\right)$. Obie ostatnie granice dotyczą$\sqrt{\frac{2\pi}{\sqrt{27}}}k^{-1/2}\approx 1.1 k^{-1/2}$.

Ale te odniesienia są stare i od tego czasu można by poczynić pewien postęp.

Powinniśmy byli $\delta_2(k)\approx \sqrt{\frac{2\pi}{\sqrt{27}}}k^{-1/2}$ asymptotycznie, patrz poniżej.

Dolna granica. Dany$k$, Zakłada zasada Pigeonhole $\delta_2(k)\ge d(k+1)/2$, gdzie $d(k+1)$ być maksymalną możliwą minimalną odległością między $k+1$punkty dysku jednostkowego, patrz ten wątek. Takie podejście powinno zapewnić asymptotyczne wiązanie$\delta_2(k)\ge\approx \sqrt{\tfrac {2\pi}{3\sqrt{3}k}}\approx 1.1 k^{-1/2}$.

Górna granica. Pozwolić$C$ a być (niekoniecznie wypukłym) podzbiorem płaszczyzny, która zawiera przystającą kopię każdego płaskiego zestawu średnicy jednostkowej i $a$ być obszarem $S$. Najbardziej znane granice$a$ są na temat $0.8441$, zobacz wątek o trudnym i niewdzięcznym dla nich poszukiwaniu. Jeśli$C$ można pokryć $k$ komórki siatki sześciokątnej z bokiem $d$ następnie $\delta_2(k)\le 2d$. Takie podejście powinno zapewnić asymptotyczne wiązanie$\delta_2(k)\le\approx 2\sqrt{\tfrac {2a}{3\sqrt{3}k}}\approx 1.14 k^{-1/2}$.

Ale Lenza sugeruje, że nie musimy używać uniwersalnego zestawu pokrywającego, ponieważ na str. 11 [Lit] pokazano, że „obszar o (największej) średnicy nie większej niż $1$ jest najwyżej $\tfrac{\pi}4$”.

Ta obserwacja powinna wskazywać na asymptotycznie ścisłą górną granicę.

Bibliografia

[Bor1] K. Borsuk, Über die Zerlegung einer euklidischen$n$-dimensionalen Vollkugel w $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 incribing$n$zbiory wymiarowe są regularne $n$-simplex , Proc. Amer. Math. Soc. 4 (1953) 222–225.

[Gra] RL Graham, Na partycjach trójkąta równobocznego , Canadian Journ. Math. 19 (1967) 394–409.

[Gru] B. Grünbaum, Etiudy w geometrii kombinatorycznej i teorii ciał wypukłych , Moskow, Nauka, 1971, w języku rosyjskim.

[KK] I. Kokorev, L. Kurlyandchik, Duży placek na małych talerzach , 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 Mathematic's Miscellaneous , Methued & Co, Londyn, wydane po raz pierwszy w 1953 roku.

[SCY] DO Shklyarskiy, NN Chentsov, IM Yaglom, Geometrical estymations and combinatorial geometry problems , Moskow, Nauka, 1974, po rosyjsku.

[Sel] JL Selfridge, Nieformalne seminarium o pokryciach zbiorów wypukłych (Report of the Inst. In the Theory of Numbers), Kolorado, 1959. 334.