Pakowanie sfer skończonych

W matematyce teoria upakowania skończonych kul dotyczy pytania, w jaki sposób można najskuteczniej upakować skończoną liczbę kul jednakowej wielkości. Kwestia upakowania skończenie wielu sfer została szczegółowo zbadana dopiero w ostatnich dziesięcioleciach, a większość prac przygotowawczych położył László Fejes Tóth .

Podobny problem dla nieskończenie wielu sfer ma dłuższą historię badań, z której najbardziej znana jest hipoteza Keplera . Atomy w strukturach krystalicznych można w uproszczeniu postrzegać jako ściśle upakowane kule i traktować jako nieskończone upakowania kul ze względu na ich dużą liczbę.

Rozróżnia się problemy związane z pakowaniem kulek między opakowaniami w danych pojemnikach i opakowaniami swobodnymi. W tym artykule omówiono przede wszystkim bezpłatne opakowania.

Pakowanie i wypukłe łuski

Wypukły kadłub w kolorze niebieskim

Ogólnie upakowanie odnosi się do dowolnego ułożenia zestawu połączonych przestrzennie obiektów o różnych rozmiarach lub kształtach w przestrzeni, tak że żaden z nich nie zachodzi na siebie. W przypadku problemu upakowania sfer skończonych obiekty te są ograniczone do kul o równych rozmiarach. Takie upakowanie kulek określa określoną objętość zwaną otoczką wypukłą opakowania, zdefiniowaną jako najmniejszy zbiór wypukły obejmujący wszystkie kule.

Pakowanie kształtów

Istnieje wiele możliwych sposobów układania kul, które można podzielić na trzy podstawowe grupy: kiełbasa, pizza i opakowanie klastrowe.

• 

  Pakowanie kiełbasy

• 

  Pakowanie pizzy

• 

  Pakowanie klastrów

Pakowanie kiełbasy

Układ, w którym środek wszystkich kul leży na jednej linii prostej, nazywa się opakowaniem kiełbasy , ponieważ wypukła otoczka ma kształt przypominający kiełbasę. Przybliżonym przykładem z prawdziwego życia jest upakowanie piłek tenisowych w tubie, chociaż końce muszą być zaokrąglone, aby tuba pokrywała się z rzeczywistym wypukłym kadłubem.

Pakowanie pizzy

Jeśli wszystkie punkty środkowe leżą na płaszczyźnie, opakowanie jest opakowaniem do pizzy . Przybliżone rzeczywiste przykłady tego rodzaju pakowania obejmują kule bilardowe pakowane w trójkąt podczas ich ustawiania. Dotyczy to opakowań w trójwymiarowej przestrzeni euklidesowej.

Pakowanie klastrów

Jeśli punkty środkowe kul są rozmieszczone w przestrzeni 3D, upakowanie nazywa się upakowaniem klastrów . Rzeczywiste przybliżenia obejmują pakowanie owoców w wielu warstwach w pudełku.

Zależności między rodzajami opakowań

Zgodnie z podanymi definicjami każde opakowanie do kiełbasy jest technicznie również opakowaniem do pizzy, a każde opakowanie do pizzy jest technicznie również opakowaniem zbiorczym. W bardziej ogólnym przypadku $-wymiarowych$$„$ ” odnoszą się do układów jednowymiarowych, „klastry” do układów , a „pizze” do tych z liczbą pośrednią. wymiarów.

Z jednej lub dwóch kul zawsze powstaje kiełbasa. Przy trzech możliwe staje się pakowanie pizzy (które nie jest jednocześnie kiełbasą), a przy czterech lub więcej możliwe stają się klastry (które również nie są pizzami).

Optymalne opakowanie

Pusta przestrzeń między kulkami różni się w zależności od rodzaju opakowania. Ilość pustej przestrzeni mierzona jest gęstością upakowania , która jest zdefiniowana jako stosunek objętości kulek do objętości całej otoczki wypukłej. Im większa gęstość upakowania, tym mniej pustej przestrzeni w wypełnieniu, a tym samym mniejsza objętość kadłuba (w porównaniu do innych wypełnień o tej samej liczbie i wielkości kulek).

Aby skutecznie upakować kule, można zadać pytanie, które opakowanie ma największą możliwą gęstość. Łatwo zauważyć, że takie upakowanie powinno mieć tę właściwość, że kule leżą obok siebie, to znaczy każda kula powinna stykać się z drugą na powierzchni. Dokładniejsze sformułowanie polega na utworzeniu wykresu , który przypisuje wierzchołek każdej kuli i łączy wierzchołki z krawędziami, ilekroć odpowiednie kule stykają się ze sobą. Wtedy upakowanie o największej gęstości musi spełniać właściwość, że odpowiadający mu wykres jest spójny .

Kiełbasa katastrofa

Z trzema lub czterema kulami pakowanie kiełbasy jest optymalne. Uważa się, że dotyczy to każdego $displaystyle$ 55 $55}$ wraz z ${\ displaystyle n=57,58,63,64}$ . Dla ${\ Displaystyle n = 56,59,60,61,62}$ i ${\ Displaystyle n \ geq 65}$ istnieje opakowanie klastrowe, które jest bardziej wydajne niż pakowanie kiełbasy, jak pokazali w 1992 roku Jörg Wills i Pier Mario Gandini. Nie wiadomo, jak wyglądają te najwydajniejsze opakowania klastrowe. Na przykład w przypadku wiadomo, że optymalnym upakowaniem nie jest upakowanie czworościenne $jak$ upakowanie kul armatnich, ale prawdopodobnie jakiś oktaedryczny .

Nagłe przejście do optymalnego kształtu opakowania jest żartobliwie nazywane przez niektórych matematyków katastrofą kiełbasy (Wills, 1985). Katastrofa desygnacyjna wynika z faktu, że optymalny kształt opakowania nagle zmienia się z uporządkowanego opakowania kiełbasy na stosunkowo nieuporządkowane opakowanie klastra i odwrotnie, gdy przechodzi się od jednego numeru do drugiego, bez zadowalającego wyjaśnienia, dlaczego tak się dzieje. Mimo to przejście w trzech wymiarach jest stosunkowo łagodne; w $przypuszcza się,$ nagłe przejście nastąpi około 377 000 kul

Dla wymiarów $optymalnym$ opakowaniem jest zawsze kiełbasa lub grono, a Otwartym problemem jest to, czy odnosi się to do wszystkich wymiarów. Wynik ten dotyczy tylko sfer, a nie innych ciał wypukłych; $wypukły kształt,$ że dla dowolnego wymiaru którego najbliższym opakowaniem jest pizza.

Przykład nieoptymalnego pakowania kiełbasy

W następnej sekcji pokazano, że dla 455 kulek upakowanie kiełbasy nie jest optymalne i zamiast tego istnieje specjalne upakowanie klastra, które zajmuje mniejszą objętość.

Objętość wypukłej osłony opakowania kiełbasy z $kulami$ promieniu $.$ obliczyć za pomocą elementarnej geometrii Środkowa część kadłuba to cylinder o długości, $\ Displaystyle h =$ gdy czapki na końcach to półkule o promieniu $r$ . Całkowita objętość jest zatem określona przez ${\ Displaystyle V_ {W}} .$

${\ Displaystyle {\ rozpocząć {wyrównane} V_ {W} i = V _ {\ tekst {cylinder}} + 2 \ cdot V_ {\ tekst {półkula}} \\& =V_{\text{cylinder}}+V_{\text{kula}}\\&=\pi hr^{2}+{\frac {4}{3}}\pi r^{3}\\& =\pi 2r\cdot (n-1)\cdot r^{2}+{\frac {4}{3}}\pi r^{3}\\&=2\cdot \left(n-{\ frac {1}{3}}\right)\pi r^{3}\end{wyrównane}}}$

Podobnie można znaleźć objętość wypukłej otoczki czworościennego upakowania, w którym kule są ułożone tak, że tworzą czworościenny kształt , co prowadzi do całkowicie wypełnionych czworościanów tylko dla określonej liczby kul. Jeśli wzdłuż jednej krawędzi czworościanu znajdują się kule, całkowita liczba $n}$ jest dana przez $displaystyle$

${\ Displaystyle n = \ suma _ {i=1}^{x}\sum _{j=1}^{i}j=\sum _{i=1}^{x}{\frac {i\cdot (i+1)}{2 }}={\frac {x\cdot (x+1)\cdot (x+2)}{6}}}$ .

Teraz promień czworościanu o długości boku $a}$ r $displaystyle$

${\ Displaystyle r = {\ Frac {\ sqrt {6}} {12}} \ cdot a}$ .

Z tego mamy

${\ Displaystyle a = 2 {\ sqrt {6}} \ cdot r}$ .

Objętość czworościanu jest wtedy dana wzorem ${\ displaystyle V_ {T}}$

${\ Displaystyle V_ {T} = {\ Frac {\ sqrt {2}} {12}} \ cdot a ^ {3} = {\ sqrt {192}} \cdot r^{3}}$

W przypadku wielu kul ułożonych wewnątrz czworościanu długość krawędzi $za$ się o dwukrotność promienia kuli dla każdej nowej warstwy, co oznacza, że ​​dla warstw długość boku staje się $\ displaystyle a}$

${\ Displaystyle a = 2 \ cdot \ lewo (x-1 + {\ sqrt {6}} \ prawej) \ cdot r}$ .

Podstawiając tę ​​​​wartość do wzoru na objętość czworościanu, wiemy, że objętość wypukłej otoczki musi być mniejsza niż sam czworościan, więc ${\ displaystyle V}$

${\ Displaystyle V <{\ Frac {2 \ cdot \ lewo (x-1 + {\ sqrt {6}} \ prawo) ^ {3 }\cdot {\sqrt {2}}\cdot r^{3}}{3}}}$ .

$wypukłej łuski$ liczbę kulek w czworościanie $i$ podstawiając do wcześniejszego wyrażenia, aby uzyskać objętość kiełbasy z taką samą liczbę kul mamy

${\ Displaystyle V _ {\ tekst {W}} = {\ Frac {x \ cdot (x + 1) \ cdot ( x+2)-2}{3}}\cdot \pi r^{3}}$ .

Dla ${\ Displaystyle x = 13}$$3$${\ Displaystyle r ^ {3}}$ na , współczynnik przed wynosi około 2845 dla czworościennego upakowania i 2856 dla opakowania kiełbasy, co oznacza, że ​​dla tej liczby kul czworościan jest bardziej upakowany.

Możliwe jest również przy odrobinie większego wysiłku wyprowadzenie dokładnego wzoru na objętość czworościennej wypukłej otoczki $, co wymagałoby odjęcia nadmiarowej$ w rogach i krawędziach czworościanu. Pozwala to na udowodnienie, że opakowanie kiełbasy jest nieoptymalne dla mniejszych wartości, $displaystyle$ zatem $n}$ .

Przypuszczenie kiełbasy

Termin kiełbasa pochodzi od matematyka László Fejesa Tótha , który w 1975 roku postawił hipotezę kiełbasy , która dotyczy uogólnionej wersji problemu do sfer, wypukłych powłok i objętości w wyższych wymiarach. $wymiarach$ kula w to $graniczny$ leży równie daleko od punktu środkowego. Przypuszczenie kiełbasy Fejesa Tótha stwierdza następnie, że od $góry zawsze$ ułożenie kulek wzdłuż linii prostej Oznacza to, że katastrofa z kiełbasą nie występuje już, gdy przekroczymy 4 wymiary. Ogólne przypuszczenie pozostaje otwarte. Jak dotąd najlepsze wyniki uzyskali Ulrich Betke i Martin Henk, którzy udowodnili hipotezę dla wymiarów 42 i większych.

Gęstość parametryczna i metody pokrewne

Chociaż można udowodnić, że opakowanie kiełbasy nie jest optymalne dla 56 kulek i że musi istnieć jakieś inne opakowanie, które jest optymalne, to nie wiadomo, jak wygląda opakowanie optymalne. Trudno jest znaleźć optymalne upakowanie, ponieważ nie ma „prostego” wzoru na objętość dowolnie ukształtowanego klastra. Optymalność (i nieoptymalność) jest pokazana poprzez odpowiednie oszacowania objętości, przy użyciu metod z geometrii wypukłej , takich jak nierówność Brunna-Minkowskiego , mieszane objętości Minkowskiego i wzór Steinera . Kluczowym krokiem w kierunku ujednolicenia teorii zarówno skończonych, jak i nieskończonych (kratowych i niesieciowych) upakowania sfer było wprowadzenie gęstości parametrycznych przez Jörga Willsa w 1992 r. Gęstość parametryczna uwzględnia wpływ krawędzi upakowania.

Użyta wcześniej definicja gęstości dotyczy objętości wypukłej otoczki kul (lub ciał wypukłych): ${\ displaystyle K}$ :

${\ Displaystyle \ delta (K, C_ {n}) = {\ Frac {nV (K)} {V (C_ {n} +K)}}}$

gdzie $jest$ wypukłym kadłubem $punktów$ środkowych $i$$}$ ( zamiast kuli, możemy również wziąć dowolne wypukłe ciało dla ${\ displaystyle K}$ ). W przypadku układu liniowego (kiełbasa) wypukła otoczka jest odcinkiem linii przechodzącym przez wszystkie punkty środkowe kul. Znak plus we wzorze odnosi się do $że$ zestawów przez Minkowskiego, tak odnosi kul

Ta definicja działa w dwóch wymiarach, gdzie Laszlo Fejes-Toth, Claude Rogers i inni wykorzystali ją do sformułowania zunifikowanej teorii opakowań skończonych i nieskończonych. W trzech wymiarach Wills podaje prosty argument, że taka ujednolicona teoria nie jest możliwa w oparciu o tę definicję: Najgęstszym skończonym układem monet w trzech $z$ . Jednak optymalnym układem nieskończonym jest układ sześciokątny z $nieskończonej nie można$ jako granicy wartości skończonych Aby rozwiązać ten problem, Wills wprowadza modyfikację definicji, dodając parametr dodatni: ${\ displaystyle \ rho}$ :

${\ Displaystyle \ delta (K, C_ {n}) = {\ Frac {nV (K)} {V (C_ {n} }+\rho K)}}}$

${\ displaystyle \ rho}$ pozwala wziąć pod uwagę wpływ krawędzi (nadając wypukłemu kadłubowi określoną grubość). Następnie łączy się to z metodami z teorii mieszanych objętości i geometrii liczb Hermanna Minkowskiego .

re ${\ Displaystyle d \ geq 2}$ istnieją wartości parametrów ${\ Displaystyle \ rho _ {s} (d)}$ ρ $\ Displaystyle \ rho _ {c } (d)}$$całkowitych$ , że dla $n$ jest najgęstszym upakowaniem (dla wszystkich liczb ) podczas $_$$_$ _ _ Te parametry są specyficzne dla wymiaru. ${\ Displaystyle \ rho _ {c} (2) = \ rho _ {s} (2) = {\ Frac {\ sqrt$ do , aby nastąpiło przejście od kiełbasek do klastrów (katastrofa kiełbasy).

Istnieje nierówność:

${ \ Displaystyle {\ Frac {V (B ^ {d})} {2V (B ^ {d-1})}} {\ rho _ {c} (d)} ^ {1-d} \ równoważnik \ delta ( B^{d})\leq {\frac {V(B^{d})}{2V(B^{d-1})}}{\rho _{s}(d)}^{1-d }}$

$V (B ^ {d})}$ objętość kuli jednostkowej $re$ wymiarach $Displaystyle$ V . re ${\ Displaystyle d = 2}$ ρ $Displaystyle \ rho _ {s} (d) = \ rho _ {c} (d)$ } przewiduje się, że dotyczy to wszystkich wymiarów, w $Displaystyle \ rho _ {$ na podstawie wartości $)}$ .