Împachetarea cercurilor

În geometrie împachetarea cercurilor este studiul aranjamentului cercurilor (de dimensiuni egale sau diferite) pe o suprafață dată, astfel încât să nu aibă loc suprapuneri și astfel încât niciun cerc să nu poată fi mărit fără a crea o suprapunere. Densitatea împachetării, $η$ , asociată unui aranjament este proporția suprafeței acoperite de cercuri. Se pot face generalizări în dimensiuni mai mari — pentru spațiul tridimensional aceasta se numește împachetarea sferelor^⁠(d), care de obicei se ocupă doar de sfere identice.

Ramura matematicii cunoscută sub denumirea de împachetarea cercurilor se ocupă de geometria și combinatorica de împachetare a cercurilor de dimensiuni arbitrare: acestea dau naștere la analogi discreți ai transformării conforme, suprafețelor Riemann^⁠(d) și a altora asemenea.

Cea mai densă împachetare

Cercuri identice aranjate într-o împachetare hexagonală, cea mai densă împachetare posibilă

Împachetarea hexagonală prin aranjarea naturală a cercurilor egale cu tranziție la o aranjare neregulată a cercurilor inegale

În planul euclidian bidimensional, Joseph Louis Lagrange a demonstrat în 1773 că cea mai mare densitate a împachetării cercurilor este aranjamentul hexagonal,^[1] în care centrele cercurilor sunt dispuse într-o rețea hexagonală (rânduri eșalonate, ca un fagure), iar fiecare cerc este înconjurat de alte 6 cercuri. Pentru cercurile cu diametrul $D$ și hexagoane cu lungimea laturii $D$ , aria hexagonului și respectiv aria cercului (de fapt a discului — și în restul articolului se va înțelege la fel) sunt:

A_{H}={\tfrac {3{\sqrt {3}}}{2}}D^{2}

A_{C}={\tfrac {\pi }{4}}D^{2}

.

Aria acoperită în fiecare hexagon de către cerc este:

A_{HC}=3A_{C}={\tfrac {3\pi }{4}}D^{2}

.

În final, densitatea împachetării este:

\eta =A_{HC}/A_{H}={\frac {3\pi }{4}}D^{2}{\big /}{\frac {3{\sqrt {3}}}{2}}D^{2}={\frac {\pi {\sqrt {3}}}{6}}\approx 0,906900.

În 1890 Axel Thue a publicat o demonstrație că aceeași densitate este optimă dintre toate împachetările, nu doar împachetarea în rețea, dar demonstrația sa a fost considerată de unii ca fiind incompletă. Prima demonstrație riguroasă este atribuită lui László Fejes Tóth în 1942.^[1]^[2]

Deși cercul are o densitate maximă de împachetare relativ scăzută, nu are cea mai mică posibilă, chiar și dintre formele convexe: octogonul netezit are o densitate de împachetare de aproximativ 0,902414, cea mai mică cunoscută pentru formele convexe cu simetrie față de centru și presupusă că este cea mai mică posibilă.^[3] (Densitățile de împachetare ale formelor concave, cum ar fi poligoanele stelate pot fi oricât de mici.)

Alte împachetări

La cealaltă extremă, Böröczky a demonstrat că există aranjamente ale cercurilor împachetate rigid cu densitate oricât de scăzută.^[4]^[5]

Există 11 împachetări ale cercurilor bazate pe cele 11 pavări uniforme ale planului.^[6] În aceste împachetări, fiecare cerc poate fi aplicat pe fiecare alt cerc prin reflexii și rotații. Golurile hexagonale pot fi umplute cu un cerc, iar golurile dodecagonale pot fi umplute cu 7 cercuri, creând 3 împachetări uniforme. Pavarea trihexagonală trunchiată, cu ambele tipuri de goluri, poate fi umplută ca o împachetare 4-uniformă. Pavarea hexagonală snub are două forme, în oglindă.

Împachetări 1-uniforme bazate pe pavări uniforme
Triunghiulară	Pavare pătrată	Pavare hexagonală	Pavare triunghiulară alungită
Trihexagonală	Pătrată snub	Pătrată trunchiată	Hexagonală trunchiată
Rombitrihexagonală	Hexagonală snub	Hexagonală snub (în oglindă)	Trihexagonală trunchiată

Pe sferă

O problemă înrudită este de a determina aranjamentul cu cea mai mică energie a punctelor care interacționează identic constrânse să se afle într-o suprafață dată. Problema Thomson^⁠(d) se ocupă cu cea mai scăzută distribuție de energie a sarcinilor electrice identice pe suprafața unei sfere. Problema Tammes^⁠(d) este o generalizare a acesteia, care se ocupă de maximizarea distanței minime dintre cercuri pe sferă. Acest lucru este analog cu distribuirea sarcinilor nepunctuale pe o sferă.

În zone mărginite

Cincisprezece cercuri egale împachetate în cel mai mic pătrat posibil. Doar patru triunghiuri echilaterale sunt formate de cercuri adiacente.

Împachetarea cercurilor în forme simple mărginite este un tip comun de problemă în matematica recreativă. Influența pereților containerului este importantă, iar pentru un număr mic de cercuri împachetarea hexagonală nu este în general optimă. Problemele specifice de acest tip care au fost studiate cuprind împachetarea în cerc, pătrat și triunghi echilateral sau isoscel dreptunghic.

Cercuri inegale

O împachetare compactă cu două dimensiuni potrivite de cercuri.^[7] Este, de asemenea, cea mai densă împachetare posibilă a discurilor cu acest raport dimensional (0,6375559772, cu densitatea împachetării de 0,910683).^[8]

De asemenea, există o serie de probleme care permit dimensiunilor cercurilor să fie neuniforme. O astfel de extensie este găsirea densității maxime posibile a unui sistem cu două dimensiuni specificate ale cercurilor (un sistem binar). Doar nouă rapoarte specifice ale razelor permit o împachetare compactă, adică în care fiecare pereche de cercuri în contact este în contact cu alte două cercuri (când segmentele de dreaptă sunt trasate de la centrul cercului contactat la centrul cercului curent, ele triangulează suprafața).^[7] Pentru toate aceste combinații de discuri cu acele rapoarte ale razelor este cunoscută câte o împachetare compactă care realizează o fracție de acoperire (densitate a împachetării) maximă posibilă (peste cea a discurilor de dimensiuni uniforme).^[9] Toate cele nouă împachetări au densități ale împachetării mai mari decât împachetarea hexagonală uniformă, la fel cu unele cu anumite rapoarte ale razelor, fără ca împachetarea să fie compactă.^[10]

De asemenea, se știe că dacă raportul razelor este peste 0,742, printr-o combinație binară nu se pot realiza împachetări mai bune decât pentru discurile de dimensiuni uniforme.^[8] Se cunosc și limitele superioare pentru densitatea care poate fi obținută în astfel de împachetări binare cu rapoarte ale razelor mai mici.^[11]

Aplicații

Modulația amplitudinii în cuadratura^⁠(d) se bazează pe împachetarea cercurilor în cercuri într-un spațiu fază-amplitudine. Un modem transmite date ca o serie de puncte într-un plan bidimensional de fază-amplitudine. Distanța dintre puncte determină toleranța la zgomot a transmisiei, în timp ce diametrul cercului circumscris determină puterea de transmisie necesară. Performanța este maximizată atunci când constelația de puncte de cod formează centrele unei împachetări a cercurilor eficientă. În practică, pentru a simplifica decodificarea adesea sunt folosite împachetări dreptunghiulare, care însă sunt suboptime.

Împachetarea cercurilor a devenit un instrument esențial în designul origami, deoarece fiecare anexă a unei figuri origami necesită un cerc de hârtie.^[12] Robert J. Lang a folosit matematica împachetării cercurilor pentru a dezvolta programe de calculator care ajută la proiectarea figurilor origami complexe.

Note

^ ^a ^b en Chang, Hai-Chau; Wang, Lih-Chung (2010). „A Simple Proof of Thue's Theorem on Circle Packing”. arXiv:1009.4322  [math.MG].
^ de Tóth, László Fejes (1942). „Über die dichteste Kugellagerung”. Math. Z. 48: 676–684. doi:10.1007/BF01180035.
^ en Eric W. Weisstein, Smoothed Octagon la MathWorld.
^ de Böröczky, K. (1964). „Über stabile Kreis- und Kugelsysteme”. Annales Universitatis Scientiarum Budapestinensis de Rolando Eötvös Nominatae, Sectio Mathematica. 7: 79–82.
^ en Kahle, Matthew (2012). „Sparse locally-jammed disk packings”. Annals of Combinatorics. 16 (4): 773–780. doi:10.1007/s00026-012-0159-0.
^ en Williams, Robert (1979). The Geometrical Foundation of Natural Structure: A Source Book of Design, Dover Publications, Inc. pp. 35–39, ISBN: 0-486-23729-X
^ ^a ^b en Tom Kennedy (2006). „Compact packings of the plane with two sizes of discs”. Discrete and Computational Geometry. 35 (2): 255–267. arXiv:math/0407145  . doi:10.1007/s00454-005-1172-4.
^ ^a ^b en Heppes, Aladár (1 august 2003). „Some Densest Two-Size Disc Packings in the Plane”. Discrete and Computational Geometry. 30 (2): 241–262. doi:10.1007/s00454-003-0007-6  .
^ en Bédaride, Nicolas; Fernique, Thomas (17 februarie 2020). „Density of Binary Compact Disc Packings”. arXiv:2002.07168  .
^ en Kennedy, Tom (21 iulie 2004). „Circle Packings”. Accesat în 11 octombrie 2018.
^ en de Laat, David; de Oliveira Filho, Fernando Mario; Vallentin, Frank (12 iunie 2012). „Upper bounds for packings of spheres of several radii”. Forum of Mathematics, Sigma. 2. arXiv:1206.2608  . doi:10.1017/fms.2014.24.
^ en TED.com lecture on modern origami "Robert Lang on TED Arhivat în 15 octombrie 2011, la Wayback Machine.."

Bibliografie

en Rajpoot, Harish Chandra (august 2022). „Mathematical analysis of 2D packing of circles on bounded and unbounded planes”. Cornell University. arXiv:2208.08222  .
en Wells D (1991). The Penguin Dictionary of Curious and Interesting Geometry. New York: Penguin Books. pp. 30–31, 167. ISBN 0-14-011813-6.
en Stephenson, Kenneth (decembrie 2003). „Circle Packing: A Mathematical Tale” (PDF). Notices of the American Mathematical Society. 50 (11). Arhivat din original (PDF) la 7 mai 2021. Accesat în 2 noiembrie 2022.

Portal Matematică

[ChangWang-1] Chang, Hai-Chau; Wang, Lih-Chung (2010). „A Simple Proof of Thue's Theorem on Circle Packing”. arXiv:1009.4322  [math.MG].

[Toth-2] Tóth, László Fejes (1942). „Über die dichteste Kugellagerung”. Math. Z. 48: 676–684. doi:10.1007/BF01180035.

[3] Eric W. Weisstein, Smoothed Octagon la MathWorld.

[4] Böröczky, K. (1964). „Über stabile Kreis- und Kugelsysteme”. Annales Universitatis Scientiarum Budapestinensis de Rolando Eötvös Nominatae, Sectio Mathematica. 7: 79–82.

[5] Kahle, Matthew (2012). „Sparse locally-jammed disk packings”. Annals of Combinatorics. 16 (4): 773–780. doi:10.1007/s00026-012-0159-0.

[6] Williams, Robert (1979). The Geometrical Foundation of Natural Structure: A Source Book of Design, Dover Publications, Inc. pp. 35–39, ISBN: 0-486-23729-X

[Kennedy-7] Tom Kennedy (2006). „Compact packings of the plane with two sizes of discs”. Discrete and Computational Geometry. 35 (2): 255–267. arXiv:math/0407145  . doi:10.1007/s00454-005-1172-4.

[Heppes-8] Heppes, Aladár (1 august 2003). „Some Densest Two-Size Disc Packings in the Plane”. Discrete and Computational Geometry. 30 (2): 241–262. doi:10.1007/s00454-003-0007-6  .

[bf-9] Bédaride, Nicolas; Fernique, Thomas (17 februarie 2020). „Density of Binary Compact Disc Packings”. arXiv:2002.07168  .

[Kennedy2-10] Kennedy, Tom (21 iulie 2004). „Circle Packings”. Accesat în 11 octombrie 2018.

[11] Laat, David; de Oliveira Filho, Fernando Mario; Vallentin, Frank (12 iunie 2012). „Upper bounds for packings of spheres of several radii”. Forum of Mathematics, Sigma. 2. arXiv:1206.2608  . doi:10.1017/fms.2014.24.

[12] TED.com lecture on modern origami "Robert Lang on TED Arhivat în 15 octombrie 2011, la Wayback Machine.."

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]