Kruhové balení - Circle packing

Nejúčinnější způsob, jak spojit kruhy různých velikostí, není zřejmý.

v geometrie, kruhové balení je studium uspořádání kruhů (stejné nebo různé velikosti) na daném povrchu tak, aby nedocházelo k překrývání a aby nebylo možné zvětšit žádný kruh bez vytvoření překrytí. Přidružené hustota balení, η, uspořádání je podíl plochy pokryté kruhy. Zobecnění lze provést na vyšší dimenze - tomu se říká koule balení, která se obvykle zabývá pouze identickými sférami.

Zatímco kruh má relativně nízkou maximální hustotu balení 0,9069 na Euklidovské letadlo, nemá nejnižší možné, dokonce ani mezi centrálně symetrický konvexní tvary. "Nejhorší" takový tvar zabalit do letadla nebyl určen, ale uhlazený osmiúhelník má hustotu balení přibližně 0,902414, což je nejnižší známá maximální hustota balení jakéhokoli centrálně symetrického konvexního tvaru.^[1](Hustota balení konkávních tvarů, jako je hvězdné polygony mohou být libovolně malé.)

Odvětví matematiky obecně známé jako „kruhové balení“ se zabývá geometrií a kombinatorikou balení libovolně velkých kruhů: tyto vedou k diskrétním analogům konformní mapování, Riemannovy povrchy a podobně.

Balení v letadle

Stejné kruhy v a šestihranné balení uspořádání, nejhustší možné balení.

Šestiúhelníkové balení prostřednictvím přirozeného uspořádání stejných kruhů s přechody k nepravidelnému uspořádání nerovných kruhů.

Ve dvourozměrném euklidovském prostoru Joseph Louis Lagrange v roce 1773 dokázal, že mřížkové uspořádání kruhů s nejvyšší hustotou je šestihranný balení,^[2] ve kterém jsou středy kruhů uspořádány do a šestihranná mříž (rozložené řádky, jako plástev ) a každý kruh je obklopen dalšími 6 kruhy. Hustota tohoto uspořádání pro kruhy o průměru D, je

${ displaystyle { begin {zarovnáno} eta _ {h} & ​​= left ({ frac {3 pi} {4}} D ^ {2} div { frac {3 { sqrt {3} }} {2}} D ^ {2} vpravo) & = { frac { pi { sqrt {3}}} {6}} přibližně 0,9069. End {zarovnáno}}}$

D je také strana šestiúhelníku na prvním obrázku. První termín ${ displaystyle { frac {3 pi} {4}} D ^ {2}}$ ve výše uvedeném poměru je součet plochy všech kruhů a částečných kruhů uzavřených šestiúhelníkem. Druhý termín ${ displaystyle { frac {3 { sqrt {3}}} {2}} D ^ {2}}$ je oblast samotného šestiúhelníku.

Bylo zjištěno, že šestihranné balení stejných kruhů vyplňuje zlomek. ${ displaystyle { frac { pi} { sqrt {12}}} přibližně 0,9069}$ plochy - což se ukázalo jako maximální pro pravidelné balení Carl Friedrich Gauss v roce 1831.^[3] Později, Axel Thue poskytl první důkaz, že to bylo optimální v roce 1890, ukazující, že šestihranná mřížka je nejhustší ze všech možných kruhových obalů, pravidelných i nepravidelných. Někteří však považovali jeho důkaz za neúplný. Je připisován první přísný důkaz László Fejes Tóth v roce 1940.^[2][4]

Na druhém konci Böröczky prokázal, že existují libovolně nízkohustotní uspořádání pevně zabalených kruhů.^[5][6]

Jednotná balení

K dispozici je 11 kruhových balení založených na 11 jednotné obklady letadla.^[7] V těchto baleních lze každý kruh mapovat na každý druhý kruh odrazy a rotacemi. The šestihranný mezery mohou být vyplněny jedním kruhem a dodecagonal mezery mohou být vyplněny 7 kruhy, což vytváří 3 uniformní balení. The zkrácené trihexagonální obklady u obou typů mezer lze vyplnit jako 4 uniformní balení. The tlumit šestihranné obklady má dvě formy zrcadlového obrazu.

Balení na kouli

Souvisejícím problémem je určení nejnižšího energetického uspořádání identicky interagujících bodů, které jsou nuceny ležet na daném povrchu. The Thomsonův problém se zabývá nejnižším rozložením energie identických elektrických nábojů na povrchu koule. The Tammesův problém je zobecněním toho, co se týká maximalizace minimální vzdálenosti mezi kruhy na kouli. To je analogické s distribucí nemístních poplatků na kouli.

Balení v ohraničených oblastech

Patnáct stejných kruhů zabaleno do nejmenšího možného čtverce. Pouze čtyři rovnostranné trojúhelníky jsou tvořeny sousedními kruhy.

Obalové kruhy v jednoduchých ohraničených tvarech je běžný typ problému v rekreační matematika. Vliv stěn kontejneru je důležitý a šestihranný obal obecně není pro malý počet kruhů optimální.

Nerovné kruhy

Kompaktní binární kruh, který má co nejvíce podobně velkých kruhů.^[7] Je to také nejhustší možné balení disků s tímto poměrem velikosti (poměr 0,6375559772 s podílem balení (plošná hustota) 0,910683).^[8]

Existuje také řada problémů, které umožňují nerovnoměrné velikosti kruhů. Jedním takovým rozšířením je nalezení maximální možné hustoty systému se dvěma specifickými velikostmi kruhu (a binární Systém). Povoluje pouze devět konkrétních poloměrů kompaktní balení, což je situace, kdy je každá dvojice kontaktních kruhů ve vzájemném kontaktu se dvěma dalšími kruhy (když jsou úsečky nakresleny od kontaktu ke středu kruhu ke středu kruhu, triangulují povrch).^[7] Pro všechny tyto rádiusové poměry je známo kompaktní těsnění, které dosahuje maximálního možného podílu náplně (vyššího než u disků stejné velikosti) pro směsi disků s tímto poloměrem.^[9] Všech devět má poměrově specifické náplně hustší než jednotné šestihranné těsnění, stejně jako některé poloměry bez kompaktních těsnění.^[10]

Je také známo, že pokud je poloměrový poměr vyšší než 0,742, nemůže se binární směs zabalit lépe než disky o jednotné velikosti.^[8] Rovněž byly získány horní meze hustoty, kterou lze v takových binárních baleních dosáhnout v menších poměrech.^[11]

Aplikace

Kvadraturní amplitudová modulace je založen na balení kruhů do kruhů v rámci prostor fázové amplitudy. A modem přenáší data jako řadu bodů v 2rozměrné rovině fázové amplitudy. Rozestup mezi body určuje toleranci šumu přenosu, zatímco průměr kruhové kružnice určuje požadovaný výkon vysílače. Výkon je maximalizován, když souhvězdí kódových bodů je ve středu efektivního kruhového balení. V praxi se pro zjednodušení dekódování často používají neoptimální obdélníkové obaly.

Circle packing se stal základním nástrojem origami design, protože každý dodatek k figuře origami vyžaduje kruh papíru.^[12] Robert J. Lang využil matematiku kruhového balení k vývoji počítačových programů, které pomáhají při navrhování složitých figurek origami.

Viz také

• Apollonian těsnění
• Kruhové balení ve čtverci
• Balení kruhu v kruhu
• Inverzní vzdálenost
• Keplerova domněnka
• Malfatti kruhy
• Problém s balením

Reference

Bibliografie

• Wells D (1991). Slovník tučňáků zvědavé a zajímavé geometrie. New York: Penguin Books. str.30–31, 167. ISBN  0-14-011813-6.
• Stephenson, Kenneth (prosinec 2003). „Circle Packing: A Mathematical Tale“ (PDF). Oznámení Americké matematické společnosti. 50 (11).