Balení koule - Sphere packing

Balení koulí nachází praktické uplatnění při skládání dělové koule

v geometrie, a koule balení je uspořádání nepřekrývající se koule uvnitř obsahujícího prostoru. Uvažované koule mají obvykle stejnou velikost a prostor je obvykle třidimenzionální Euklidovský prostor. Avšak sféra problémy s balením lze zobecnit, aby zvážila nerovné sféry, prostory jiných dimenzí (kde se problém stává kruhové balení ve dvou rozměrech, nebo hypersféra balení ve vyšších rozměrech) nebo do neeuklidovský prostory jako hyperbolický prostor.

Typickým problémem s balením koulí je najít uspořádání, ve kterém koule vyplní co nejvíce prostoru. Podíl prostoru vyplněného koulemi se nazývá hustota uspořádání. Jelikož se místní hustota náplně v nekonečném prostoru může lišit v závislosti na objemu, přes který se měří, je obvykle problém maximalizovat průměrný nebo asymptotické hustota měřená na dostatečně velkém objemu.

U stejných koulí ve třech rozměrech využívá nejhustší obal přibližně 74% objemu. Náhodné balení stejných koulí má obecně hustotu kolem 64%.

Klasifikace a terminologie

A mříž uspořádání (běžně nazývané a pravidelný uspořádání) je takové, ve kterém středy koulí tvoří velmi symetrický vzor, ​​který pouze potřebuje n vektory, které mají být jednoznačně definovány (v n-dimenzionální Euklidovský prostor ). Mřížová uspořádání jsou periodická. Uspořádání, ve kterých koule netvoří mřížku (často označovanou jako nepravidelný) může být stále periodický, ale také neperiodické (správně řečeno neperiodické) nebo náhodný. Mřížová uspořádání jsou snadněji ovladatelná než nepravidelná - jejich vysoký stupeň symetrie usnadňuje jejich klasifikaci a měření jejich hustoty.

Pravidelné balení

Pravidelné uspořádání rovných koulí v rovině měnící se na nepravidelné uspořádání nerovných koulí (bublin).
Mřížka HCP (vlevo) a mřížka FCC (vpravo) jsou dvě nejběžnější uspořádání s nejvyšší hustotou.
Dva způsoby, jak stohovat tři letadla vyrobená z koulí

Husté balení

Hlavní článek: Balení stejných koulí

V trojrozměrném euklidovském prostoru je nejhustšího balení stejných koulí dosaženo pomocí rodiny struktur zvaných zabalený struktur. Jeden způsob generování takové struktury je následující. Zvažte letadlo s kompaktním uspořádáním koulí. Říkejte tomu A. U libovolných tří sousedních koulí může být nahoře v prohlubni mezi třemi spodními koulemi umístěna čtvrtá koule. Pokud to uděláme pro polovinu otvorů ve druhé rovině nad první, vytvoříme novou kompaktní vrstvu. Existují dvě možné možnosti, jak to udělat, říkat jim B a C. Předpokládejme, že jsme zvolili B. Pak jedna polovina dutin B leží nad středy koulí v A a jedna polovina leží nad dutinami A, které nebyly používá se pro B. Tudíž koule třetí vrstvy mohou být umístěny buď přímo nad koule první, čímž se získá vrstva typu A, nebo nad otvory první vrstvy, které nebyly obsazeny druhou vrstvou, čímž se získá vrstva typu C. Spojením vrstev typu A, B a C vznikají různé těsně uzavřené struktury.

Dvě jednoduchá uspořádání v těsně uzavřené rodině odpovídají běžným mřížím. Jeden se nazývá kubický těsný obal (nebo kubický střed „FCC“) - kde se vrstvy střídají v sekvenci ABCABC .... Druhé se nazývá hexagonální těsné balení („HCP“) - kde se vrstvy střídají v sekvenci ABAB .... Je ale možné mnoho sekvencí skládání vrstev (ABAC, ABCBA, ABCBAC atd.) A stále generují uzavřenou strukturu. Ve všech těchto uspořádáních se každá koule dotýká 12 sousedních koulí,[1] a průměrná hustota je

Carl Friedrich Gauss v roce 1831 prokázal, že tyto obaly mají nejvyšší hustotu mezi všemi možnými příhradovými obaly.[2]

V roce 1611 Johannes Kepler domníval se, že se jedná o maximální možnou hustotu pravidelného i nepravidelného uspořádání - toto se stalo známé jako Keplerova domněnka. V roce 1998 Thomas Callister Hales, v souladu s přístupem navrženým László Fejes Tóth v roce 1953 oznámil důkaz o domněnce Keplera. Halesův důkaz je a důkaz vyčerpáním zahrnující kontrolu mnoha jednotlivých případů pomocí složitých počítačových výpočtů. Rozhodčí uvedli, že si jsou „na 99% jisti“ správností Halesova důkazu. Dne 10. srpna 2014 Hales oznámil dokončení formálního důkazního použití automatická kontrola kontroly, odstranění jakýchkoli pochybností.[3]

Další běžné mřížkové ucpávky

Některé další mřížkové ucpávky se často nacházejí ve fyzických systémech. Patří mezi ně kubická mřížka s hustotou , hexagonální mřížka s hustotou a čtyřboká mřížka s hustotou a nejvolnější možný při hustotě 0,0555.[4]

Zaseknuté obaly s nízkou hustotou

Obaly, kde jsou všechny sféry omezeny svými sousedy, aby zůstaly na jednom místě, se nazývají tuhé nebo zaseknutý. Striktně zaseknutou sférickou náplní s nejnižší hustotou je zředěný („tunelovaný“) krystal fcc s hustotou pouze 0,49365.[5]

Nepravidelné balení

Hlavní článek: Náhodné uzavření balíčku

Pokud se pokusíme vybudovat hustě nabitou sbírku koulí, budeme v pokušení umístit vždy další kouli do prohlubně mezi tři zabalené koule. Pokud je takto sestaveno pět koulí, budou v souladu s jedním z výše popsaných pravidelně zabalených uspořádání. Takto umístěná šestá koule však způsobí, že struktura bude nekonzistentní s jakýmkoli pravidelným uspořádáním. To má za následek možnost a náhodné blízké balení kuliček, které jsou stabilní proti stlačení.[6] Vibrace náhodného volného obalu mohou mít za následek uspořádání sférických částic do běžných obalů, což je proces známý jako granulovaná krystalizace. Takové procesy závisí na geometrii nádoby, která drží sférická zrna.[1]

Když jsou koule náhodně přidány do kontejneru a poté stlačeny, budou obecně tvořit takzvanou „nepravidelnou“ nebo „zaseknutou“ konfiguraci balení, když je již nebude možné stlačit. Toto nepravidelné balení bude mít obecně hustotu asi 64%. Nedávný výzkum analyticky předpovídá, že nemůže překročit limit hustoty 63,4%[7] Tato situace je na rozdíl od případu jedné nebo dvou dimenzí, kdy komprese kolekce jednorozměrných nebo dvourozměrných koulí (tj. Úsečkových segmentů nebo kruhů) přinese pravidelné balení.

Balení hypersféry

Problém s balením koulí je trojrozměrná verze třídy problémů s balením koulí v libovolných rozměrech. Ve dvou dimenzích je ekvivalentní problém balicí kruhy V letadle. V jedné dimenzi je to balení liniových segmentů do lineárního vesmíru.[8]

V dimenzích vyšších než tři jsou nejhustší pravidelné balíčky hypersfér známé až do 8 dimenzí.[9] O nepravidelných obalech hypersféry je známo velmi málo; je možné, že v některých rozměrech může být nejhustší obal nepravidelný. Určitá podpora tohoto dohadu pochází ze skutečnosti, že v určitých rozměrech (např.10) je nejhustší známé nepravidelné balení hustší než nejhustší známé pravidelné balení.[10]

V roce 2016 Maryna Viazovska oznámil důkaz, že E8 mříž poskytuje optimální balení (bez ohledu na pravidelnost) v osmirozměrném prostoru,[11] a brzy nato ona a skupina spolupracovníků ohlásili podobný důkaz, že Mřížka pijavice je optimální ve 24 rozměrech.[12] Tento výsledek stavěl na vylepšených předchozích metodách, které ukázaly, že tyto dvě mřížky jsou velmi blízké optimálnímu.[13]Nové důkazy zahrnují použití Laplaceova transformace pečlivě zvoleného modulární funkce postavit a radiálně symetrické funkce F takhle F a jeho Fourierova transformace F oba se rovnají jedné na původ, a oba zmizí ve všech ostatních bodech optimální mřížky, s F negativní mimo centrální sféru ucpávky a F pozitivní. Poté Poissonův součtový vzorec pro F se používá k porovnání hustoty optimální mřížky s hustotou jakéhokoli jiného obalu.[14] Než byl důkaz formálně rozhodčí a publikoval, matematik Peter Sarnak nazval důkaz „úžasně jednoduchým“ a napsal, že „Prostě začnete číst článek a víte, že je to správné.“[15]

Pokouší se najít další linii výzkumu vysokých dimenzí asymptotické meze hustoty nejhustších obalů. Jak 2017, je známo, že pro velké n, nejhustší mřížka v rozměru n má hustotu mezi cn · 2-n (pro nějakou konstantu C) a 2-.599n.[16] Konjekturální hranice leží mezi nimi.[17]

Nerovné balení koule

Husté balení koulí s poloměrem 0,64799 a hustotou 0,74786[18]

Mnoho problémů v chemických a fyzikálních vědách může souviset s problémy balení, kde je k dispozici více než jedna velikost koule. Zde je na výběr mezi oddělením koulí do oblastí těsně zabalených stejných koulí nebo kombinací více velikostí koulí do sloučeniny nebo vsunutá reklama balení. Když mnoho velikostí koulí (nebo a rozdělení ) jsou k dispozici, problém se rychle stává neřešitelným, ale jsou k dispozici některé studie binárních tvrdých koulí (dvou velikostí).

Když je druhá koule mnohem menší než ta první, je možné uspořádat velké koule v těsném uspořádání a pak uspořádat malé koule do oktaedrických a čtyřbokých mezer. Hustota tohoto vsunutého obalu citlivě závisí na poměru poloměru, ale v limitu extrémních poměrů velikosti mohou menší koule vyplnit mezery se stejnou hustotou jako prostor vyplněný většími koulemi.[19] I když velké koule nejsou v těsném uspořádání, je vždy možné vložit několik menších koulí až do 0,29099 poloměru větší koule.[20]

Pokud má menší koule poloměr větší než 0,41421 poloměru větší koule, již není možné zapadnout ani do oktaedrických otvorů uzavřené struktury. Za tímto bodem se tedy musí hostitelská struktura expandovat, aby se přizpůsobila vsunutým reklamám (což ohrožuje celkovou hustotu), nebo se přeskupit do složitější struktury krystalické sloučeniny. Jsou známy struktury, které překračují těsnou těsnicí hustotu pro poměry poloměru až 0,659786.[18][21]

Rovněž byly získány horní hranice hustoty, kterou lze v takových binárních obalech získat.[22]

V mnoha chemických situacích, jako je iontové krystaly, stechiometrie je omezen náboji iontů, které ho tvoří. Toto další omezení balení spolu s nutností minimalizovat Coulombova energie interakčních poplatků vede k rozmanitosti optimálních uspořádání balení.

Hyperbolický prostor

Ačkoli koncept kruhů a koulí lze rozšířit na hyperbolický prostor, hledání nejhustšího balení se stává mnohem obtížnějším. V hyperbolickém prostoru neexistuje žádné omezení počtu koulí, které mohou obklopovat jinou sféru (například Ford kruhy lze považovat za uspořádání identických hyperbolických kruhů, ve kterých je každý kruh obklopen nekonečný počet dalších kruhů). Koncept průměrné hustoty je také mnohem obtížnější přesně definovat. Nejhustší balení v jakémkoli hyperbolickém prostoru jsou téměř vždy nepravidelná.[23]

Navzdory této obtížnosti dává K. Böröczky univerzální horní mez pro hustotu hyperbolických koulí n-prostor kde n ≥ 2.[24] Ve třech rozměrech je Böröczkyho vazba přibližně 85 327 613% a je realizována horosféra balení objednávka 6 čtyřstěnný plástev s Schläfliho symbol {3,3,6}.[25] Kromě této konfigurace nejméně tři další horosféra je známo, že existují obaly v hyperbolickém 3-prostoru, které realizují horní hranici hustoty.[26]

Dojemné páry, trojice a čtyřky

The kontaktní graf libovolného konečného balení jednotkových koulí je graf, jehož vrcholy odpovídají ucpávkovým prvkům a jehož dva vrcholy jsou spojeny hranou, pokud se odpovídající dva ucpávkové prvky navzájem dotýkají. Mohutnost sady hran kontaktního grafu udává počet dotýkajících se párů, počet 3 cyklů v kontaktním grafu udává počet dotýkajících se trojic a počet čtyřstěnů v kontaktním grafu udává počet dotýkajících se čtyřnásobků ( obecně pro kontaktní graf spojený s balením koule n rozměry, které mohutnost souboru n-simplices v kontaktním grafu udává počet doteků (n + 1) -tuples v balení koule). V případě 3-dimenzionálního euklidovského prostoru, netriviální horní hranice počtu dotýkajících se párů, trojic a čtyřčat[27] byly prokázány Karoly Bezdek a Samuel Reid z University of Calgary.

Problém nalezení uspořádání n identické koule, které maximalizují počet kontaktních bodů mezi koulemi, se nazývají „problém lepivé koule“. Maximum je známé pro n ≤ 11 a pro větší jsou známy pouze domnělé hodnoty n.[28]

Ostatní prostory

Balení koulí v rozích hyperkrychle (s koulemi definovanými pomocí Hammingova vzdálenost ) odpovídá návrhu kódy opravující chyby: pokud mají koule poloměr t, pak jejich centra jsou kódová slova a (2t + 1) - kód opravující chybu. Mřížkové těsnění odpovídá lineárním kódům. Mezi balením euklidovské sféry a kódy pro opravu chyb existují i ​​jiné, jemnější vztahy. Například binární Golay kód úzce souvisí s 24-dimenzionální mřížkou Leech.

Další podrobnosti o těchto připojeních najdete v knize Balení koule, mřížky a skupiny podle Conway a Sloane.[29]

Viz také

Reference

  1. ^ A b Granulovaná krystalizace ve vibrovaných obalech Granular Matter (2019), 21 (2), 26 Archivy HAL převyšují
  2. ^ Gauß, C. F. (1831). „Besprechung des Buchs von L. A. Seeber: Untersuchungen über die Eigenschaften der positiven ternären quadratischen Formen usw “[Diskuze o knize L. A. Seebera: Studie charakteristik pozitivních ternárních kvadratických forem atd]. Göttingsche Gelehrte Anzeigen.
  3. ^ „Dlouhodobé úložiště pro hostování projektu Google Code“. Archiv kódů Google.
  4. ^ „Wolfram Math World, Sphere packing“.
  5. ^ Torquato, S.; Stillinger, F. H. (2007). "Směrem k rušivému prahu obalů koulí: tunelované krystaly". Journal of Applied Physics. 102 (9): 093511–093511–8. arXiv:0707.4263. Bibcode:2007JAP ... 102i3511T. doi:10.1063/1.2802184. S2CID  5704550.
  6. ^ Chaikin, Paul (červen 2007). "Náhodné myšlenky". Fyzika dnes. Americký fyzikální institut. 60 (6): 8. Bibcode:2007PhT .... 60f ... 8C. doi:10.1063/1.2754580. ISSN  0031-9228.
  7. ^ Song, C .; Wang, P .; Makse, H. A. (29. května 2008). "Fázový diagram pro zaseknutou hmotu". Příroda. 453 (7195): 629–632. arXiv:0808.2196. Bibcode:2008 Natur.453..629S. doi:10.1038 / nature06981. PMID  18509438. S2CID  4420652.
  8. ^ Griffith, J.S. (1962). "Balení stejných 0 koulí". Příroda. 196 (4856): 764–765. Bibcode:1962 Natur.196..764G. doi:10.1038 / 196764a0. S2CID  4262056.
  9. ^ Weisstein, Eric W. „Hypersphere Packing“. MathWorld.
  10. ^ Sloane, N. J. A. (1998). „Problém s balením koulí“. Documenta Mathematica. 3: 387–396. arXiv:matematika / 0207256. Bibcode:2002math ...... 7256S.
  11. ^ Viazovska, Maryna (1. ledna 2017). „Problém s balením koule v dimenzi 8“. Annals of Mathematics. 185 (3): 991–1015. arXiv:1603.04246. doi:10.4007 / annals.2017.185.3.7. ISSN  0003-486X. S2CID  119286185.
  12. ^ Cohn, Henry; Kumar, Abhinav; Miller, Stephen; Radchenko, Danylo; Viazovska, Maryna (1. ledna 2017). „Problém s balením koule v dimenzi 24“. Annals of Mathematics. 185 (3): 1017–1033. arXiv:1603.06518. doi:10.4007 / annals.2017.185.3.8. ISSN  0003-486X. S2CID  119281758.
  13. ^ Cohn, Henry; Kumar, Abhinav (2009), „Optimalita a jedinečnost mřížky Leech mezi mřížemi“, Annals of Mathematics, 170 (3): 1003–1050, arXiv:math.MG/0403263, doi:10.4007 / annals.2009.170.1003, ISSN  1939-8980, PAN  2600869, S2CID  10696627, Zbl  1213.11144 Cohn, Henry; Kumar, Abhinav (2004), „Nejhustší mřížka ve dvaceti čtyřech rozměrech“, Oznámení elektronického výzkumu Americké matematické společnosti, 10 (7): 58–67, arXiv:math.MG/0408174, doi:10.1090 / S1079-6762-04-00130-1, ISSN  1079-6762, PAN  2075897, S2CID  15874595
  14. ^ Miller, Stephen D. (4. dubna 2016), Řešení problému s balením koulí ve 24 rozměrech prostřednictvím modulárních forem, Institut pro pokročilé studium. Video hodinové přednášky jednoho z Viazovských spoluautorů vysvětlujících nové důkazy.
  15. ^ Klarreich, Erica (30. března 2016), „Balení koulí vyřešeno ve vyšších dimenzích“, Časopis Quanta
  16. ^ Cohn, Henry (2017), „Koncepční průlom v balení koulí“ (PDF), Oznámení Americké matematické společnosti, 64 (2): 102–115, arXiv:1611.01685, doi:10.1090 / noti1474, ISSN  0002-9920, PAN  3587715, S2CID  16124591
  17. ^ Torquato, S .; Stillinger, F. H. (2006), „Nové hypotetické dolní meze pro optimální hustotu ucpávky koule“, Experimentální matematika, 15 (3): 307–331, arXiv:matematika / 0508381, doi:10.1080/10586458.2006.10128964, PAN  2264469, S2CID  9921359
  18. ^ A b O'Toole, P. I .; Hudson, T. S. (2011). "Nové vysokohustotní obaly binárních koulí se stejnou velikostí". The Journal of Physical Chemistry C. 115 (39): 19037. doi:10.1021 / jp206115p.
  19. ^ Hudson, D. R. (1949). "Hustota a balení v agregátu smíšených koulí". Journal of Applied Physics. 20 (2): 154–162. Bibcode:1949JAP .... 20..154H. doi:10.1063/1.1698327.
  20. ^ Zong, C. (2002). „Od hlubokých děr po volná letadla“. Bulletin of the American Mathematical Society. 39 (4): 533–555. doi:10.1090 / S0273-0979-02-00950-3.
  21. ^ Marshall, G. W .; Hudson, T. S. (2010). "Husté binární koule". Příspěvky k algebře a geometrii. 51 (2): 337–344.
  22. ^ de Laat, David; de Oliveira Filho, Fernando Mário; Vallentin, Frank (12. června 2012). "Horní hranice pro balení koulí několika poloměrů". Fórum matematiky, Sigma. 2. arXiv:1206.2608. doi:10.1017 / fms.2014.24. S2CID  11082628.
  23. ^ Bowen, L .; Radin, C. (2002). „Nejhustší balení rovných koulí v hyperbolickém prostoru“. Diskrétní a výpočetní geometrie. 29: 23–39. doi:10.1007 / s00454-002-2791-7.
  24. ^ Böröczky, K. (1978). "Balení koulí v prostorech s konstantním zakřivením". Acta Mathematica Academiae Scientiarum Hungaricae. 32 (3–4): 243–261. doi:10.1007 / BF01902361. S2CID  122561092.
  25. ^ Böröczky, K .; Florian, A. (1964). „Über die dichteste Kugelpackung im hyperbolischen Raum“. Acta Mathematica Academiae Scientiarum Hungaricae. 15 (1–2): 237–245. doi:10.1007 / BF01897041. S2CID  122081239.
  26. ^ Kozma, R. T .; Szirmai, J. (2012). "Optimálně husté ucpávky pro plně asymptotické coxeterové obklady horoballs různých typů". Monatshefte für Mathematik. 168: 27–47. arXiv:1007.0722. doi:10.1007 / s00605-012-0393-x. S2CID  119713174.
  27. ^ Bezdek, Karoly; Reid, Samuel (2013). "Kontaktní grafy obalů Sphere Revisited". Journal of Geometry. 104 (1): 57–83. arXiv:1210.5756. doi:10.1007 / s00022-013-0156-4. S2CID  14428585.
  28. ^ „The Science of Sticky Spheres“. Americký vědec. 6. února 2017. Citováno 14. července 2020.
  29. ^ Conway, John H.; Sloane, Neil J. A. (1998). Balení koule, mřížky a skupiny (3. vyd.). Springer Science & Business Media. ISBN  0-387-98585-9.

Bibliografie

externí odkazy

Netechnický přehled balení v hyperbolickém prostoru.