Körök pakolása négyzetekbe

A természettudományokban, a mérnöki tervezésben és a mindennapi életben is számos feladat vezet olyan matematikai problémához, ahol egybevágó alakzatokkal kell egy adott tartományt a legsûrûbben kitölteni.Ilyen feladat pédául, hogy helyezzünk el minél több azonos méretû hordót egy raktárban vagy vágjunk ki minél több egyforma kört egy adott méretű anyagból. Az ilyen feladatok megoldása lényegében a következõ problémára vezethetõ vissza : 
Hogyan lehet n ⩾2 egybevágó, egymásba nem nyúló körrel a sík egy korlátos tartományát kitölteni?
Programozási feladatom  tárgya ennek a nevezetes diszkrét geometriai problémának egy speciális esete, az egységnégyzetben való legsűrűbb körpakolás problémájának vizsgálata,  hogy hogyan helyezzünk el n egybevágó, egymást nem fedő kört az egységnégyzetben, hogy a sugár maximális legyen.
A körpakolás sűrűsége: d=n ((Subscript[r, n])^2) π.

Bolyai Farkas körpakolási vizsgálatai

Bolyai Farkas magyar matematikus volt az első, aki egy körpakolás sűrűségét vizsgálta korlátos tartományban. Az 1832 - 33 - ban kiadott, röviden csak' Tentamen' - ként emlegetett híres munkájában 19 körnek egy szabályos háromszögben való elhelyezésével találkozhatunk. Az általa adott körpakolást úgy kaphatjuk meg, hogy felosztjuk a háromszög oldalait 4 egyenlő részre és az osztópontokat az oldalakkal párhuzamos egyenesekkel összekötjük. Ha a keletkezett kis háromszögekben tekintjük azok beírható körét, akkor még további 3 kört tehetünk azokra a helyekre, amelyeket hat másik kör vesz körül ugyanakkora sugárral.
Bolyai Farkas az említett mûvében azt a kérdést vizsgálta, hogy ha az oldalak felosztását a végtelenhez tartjuk, akkor hogyan fog a háromszög körökkel nem fedett területe változni. A pakolás sűrűsége (π/(Sqrt[12]))-höz konvergál.

Az alábbi ábrán azt mutatom be, hogy egy szabályos háromszögben Bolyai Farkas módszerét alkalmazva hogyan tudunk elhelyezni köröket. k a háromszög egy oldalán lévő osztópontok száma.

pontok1[k_]:=Table[{i/(2 k),i Sqrt[3]/(2 k)},{i,0,k}]
pontok2[k_]:=Table[{1-i/(2 k),i Sqrt[3]/(2 k)},{i,0,k}]
pontok3[k_]:=Join[Tuples[{Table[i/(2 k),{i,1,2k,2}],Table[i Sqrt[3]/(6 k),{i,1,3k,2}]}],Tuples[{Table[i/k,{i,0,k}],Table[i Sqrt[3]/(6 k),{i,2,3k,2}]}]]
f[a_List,b_List]:=Table[{a[[i]],b[[i]]},{i,1,Length[a]}]
g[{x_,y_}]:=If[y<Sqrt[3] x&& y<Sqrt[3]-Sqrt[3] x,{x,y}]
Manipulate[Show[Graphics[Line[f[pontok1[k],pontok2[k]]]],Graphics[Rotate[Line[f[pontok1[k],pontok2[k]]],120 Degree,{1/2,Sqrt[3]/6}]],Graphics[Rotate[Line[f[pontok1[k],pontok2[k]]],-120 Degree,{1/2,Sqrt[3]/6}]],Graphics[{Green,Circle[#,Sqrt[3]/(6 k)]}&/@Cases[Map[g,pontok3[k]],{_,_}]]],{k,1,10,1}]

Ismétlődő minták a körpakolásokban

Az optimális és az eddig ismert legjobb körpakolások struktúráinak összehasonlítása alapján kiderült, hogy bizonyos esetekben ismétlődő miták fedezhetőek fel. Az ismétlődő minták és a  körök darabszáma között gyakran kapcsolat van. Ezen kapcsolat alapján bizonyos körpakolásokat mintaosztályokba sorolhatunk. Az alábbi mintaosztályok csak véges sok esetre adnak optimális megoldást, de ezen mintaosztályok alapján az elméleti úton a sűrűségre kapott alsó és felső korlátokat tovább javíthatjuk.

A mintaosztályokra, és a hozzájuk tartozó mintákra használni fogom a PAT (f (k)) jelölést, ahol  f: ℕ → ℕ egy adott függvény és f (k) a körök számát jelenti. 
Minden körpakolás megfeleltethető egy pontelhelyezésnek, ahol a pontok közötti minimális m távolságot szeretnénk maximalizálni. Ekkor m=((2r)/(1-r)).

A PAT ((k^2)) mintaosztály

A legszembetűnőbb mintát az n = 1, 4, 9, 16, 25 és 36 négyzetszámokhoz tartozó, a köröket négyzetes struktúrában elhelyező körpakolások adják. Ezeben az esetekben bizonyítottan ez a minta adja az optámális körpakolást. k=7 esetén pedig biztosan nem. Ebbe az osztályba tartozó körpakolások sűrűsége állandó ((Subscript[d, n])=(((k^2)((1/(2k))))^2)π=(π/4)).

A PAT((k^2)) mintájú pontelhelyezésekben minden k≥2 esetén (Subscript[m, n]) = (1/(k-1)).

Az alábbi ábrán k = 1, 2, 3, 4, 5 és 6 esetén kirajzolom az elrendezést.

Manipulate[Show[Graphics[Line[{{0,0},{0,1},{1,1},{1,0},{0,0}}]],Graphics[{Red,Circle[#,1/(2 k)]}&/@ Tuples[Table[(2 i-1)/(2 k),{i,1,k}],2]]],{{k,3,"circle"},1,6,1}]

A PAT((k^2)-1) mintaosztály

Helyezzünk el a négyzetben n = (k^2) darab kört (n≥3) a PAT ((k^2)) mintának megfelelően, majd vegyünk ki egy olyan kört a pakolásból, amely nem érintkezik a négyzet egyetlen oldalával sem.Az így megmaradt (k^2)-1 darab kör már elhelyezhető egy kisebb oldalhosszúságú négyzetben is, ha a kiválasztott kör oszlopában (illetve sorában) lévő köröket az egységnégyzet (0, 0) - (0, 1) (illetve (0, 0) - (1, 0)) oldalaival párhuzamosan beljebb toljuk és az egész körpakolást összenyomjuk úgy, hogy a kivett kört érintő körök középpontjai egy rombuszt alkossanak.

A PAT((k^2)-1) mintájú pontelhelyezésekben minden k≥3 esetén (Subscript[m, n]) = (1/(k-3+(Sqrt[2+(Sqrt[3])]))).

Igazolható, hogy a k = 3, 4 és 5 esetekben az így kapott körpakolások optimálisak lesznek. Ez a minta sejthetően ad egy optimális körpakolást a k = 6 (n = 35) esetben is, az n = 48-ra azonban biztosan nem.

A következő ábrán a k=3,4, 5 és 6 esetekben az optimális körpakolás látható.

ClearAll;
l[k_]:=1/(k-3+Sqrt[2+Sqrt[3]])
r[k_]:=l[k]/(2 (l[k]+1))
Manipulate[Show[Graphics[Circle[#,r[k]]&/@Join[Table[{r[k],i r[k]},{i,1, 2 k-4,2}],{{r[k],1-r[k]}},Flatten[Table[{1-i r[k],j r[k]},{i,1, 2 k-4,2},{j,1, 2 k-4,2}],1],Table[{1-i r[k],1-r[k]},{i,1, 2 k-4,2}],Table[{r[k]+Cos[15 Degree] 2 r[k],i r[k]+Sin[15 Degree] 2 r[k]},{i,1,2 k-4,2}],{{r[k]+2 r[k] Sin[15 Degree],1-r[k]-Cos[15 Degree] 2 r[k]}},Table[{1-i r[k]-Sin[15 Degree] 2 r[k],1-r[k]-Cos[15 Degree] 2 r[k]},{i,1,2 k-4,2}],{{r[k]+Cos[15 Degree] 2 r[k],1-r[k]-2 r[k] Sin[15 Degree]}}]],Graphics[Line[{{0,0},{0,1},{1,1},{1,0},{0,0}}]]],{{k,3,circle},3,6,1}]

A PAT ((k^2)-2) mintaosztály

Tekintsünk a PAT ((k^2)) mintának megfelelő körpakolásban egy olyan kört, amely a négyzet valamelyik sarkában van.Vegyük ki azt a két kört a pakolásból, amelyek érintik a kiválasztott kört.A sarokban lévő kör sorában és oszlopában egyaránt k-1, k-1 kör marad, a sarokban lévő kört pedig semmilyen kör nem érinti, így az szabad körré válik. ( Egy körpakolásban egy kört szabad körnek mondunk, ha a kör középpontjának van olyan környezete, amelyen belül a középpontot mozgatva a kör a négyzet belsejében marad és nem lesz közös pontja más körrel. Az ábrán a szabad kört szinezéssel jelölöm.)
Ez a minta a k=3 és 4 esetben adja az optimális pakolásokat.

ClearAll;
l1[k_]:=1/(k-2+Sqrt[3]/2)
r1[k_]:=l1[k]/(2 (l1[k]+1))
Manipulate[Show[Graphics[Line[{{0,0},{0,1},{1,1},{1,0},{0,0}}]],Graphics[{Red,Circle[#,r1[k]]}&/@ Tuples[Table[i r1[k],{i,1,2(k-1),2}],2]],Graphics[{Red,Circle[#,r1[k]]}&/@ Table[ {i r1[k] ,1-r1[k]},{i,2,k,2}]],Graphics[{Red,Circle[#,r1[k]]}&/@ Table[ {1-r1[k],i r1[k] },{i,2,k,2}]],Graphics[{Red,Disk[#,r1[k]]}&/@ Table[ {1-r1[k],1- r1[k] },{i,2,k,2}]]],{{k,3,"circle"},3,4,1}]

A PAT(k(k+ 1)) mintaosztály

Helyezzük el a pontokat egy téglalaprácson az alábbiak szerint : 
Osszuk fel a négyzet egyik oldalát k, egy az előbbire meröleges másik oldalát 2k-1 egyenlő részre. Az osztópontokon keresztül húzzunk párhuzamosokat az oldalakkal. A kapott téglalaprácsnak tegyünk minden második rácspontjába egy pontot úgy, hogy az első pontot a négyzet (0; 0) koordinátájú sarkába tesszük.Az így lerakott k (k + 1) pont koordinátái az alábbiak lesznek :
(i/k, ((i mod 2)/(2k-1))+((2j)/(2k-1))) , ahol 0 ≤  i ≤ k és 0 ≤  j≤ k-1.
Könnyű belátni, hogy a pontok közötti minimális (Subscript[m, n]) távolság csak akkor lesz (Sqrt[(1/(k^2))+(1/(((2k-1))^2))]), vagyis pontosan a téglalap átlóhossza, ha 1 ≤ k ≤ 3. Viszont ezekben az esetekben ez a minta adja az opimális pakolásokat, míg k növekedésével már egy másik mintaosztályba tartoznak az optimális és az ismert legjobb elhelyezések.

l3[k_]:=Sqrt[1/k^2+1/(2 k-1)^2]
r3[k_]:=l3[k]/(2 (l3[k]+1))
f1[k_]:=Join[Table[r3[k]+(1-2 r3[k]) i/k,{i,0,k}]]
f2[k_]:=Join[Table[r3[k]+(1-2 r3[k]) i/(2 k-1),{i,0,2k-1}]]
f3[k_]:=Tuples[{f1[k],f2[k]}]
Manipulate[Show[Graphics[Circle[#,r3[k]]&/@Join[Table[Flatten[Table[Partition[f3[k]//N,2 k][[i]],{i,1,k+1,2}],1][[j]],{j,1,2 k (⌈k/2⌉+(Mod[k+1,2])),2}],Table[Flatten[Table[Partition[f3[k]//N,2 k][[i]],{i,2,k+1,2}],1][[j]],{j,2,2 k ⌈k/2⌉,2}]]],Graphics[Line[{{0,0},{0,1},{1,1},{1,0},{0,0}}]]],{{k,3,circle},1,3,1}]

A PAT ((k^2)+ ⌊k/2⌋) mintaosztály

A (Subscript[PAT, 1])k(k+ 1)) mintaképzéshez hasonlóan tekintsük most azt a pontelhelyezést, amikor nem k és 2k-1 részre osztjuk a négyzet oldalait, hanem k és 2k-2 egyenlő részre. Ekkor a pontelhelyezést az alábbi koordinátákkal adhatjuk meg :
((i/(k^2)),(j/(2k-2))), ahol 0≤i≤k, 0≤2k-2 és k≤7.
A pontok közötti távolságok minimuma azonban csak akkor lesz egyenlő a téglalapok átlóival, ha (k^2)-8k+4≤0.  Amint az könnyen ellenőrizhető, ekkor k≤7, ahol k pozitív egész szám. A k=2,4 és 5 esetekben az optimális, a k=6 és 7 esetekben a ma ismert legjobb pakolást adja.

l5[k_]:=Sqrt[1/k^2+1/(2 k-2)^2]
r5[k_]:=l5[k]/(2 (l5[k]+1))
h1[k_]:=Join[Table[r5[k]+(1-2 r5[k]) i/k,{i,0,k}]]
h2[k_]:=Join[Table[r5[k]+(1-2 r5[k]) i/(2 k-2),{i,0,2k-2}]]
h3[k_]:=Tuples[{h1[k],h2[k]}]
Manipulate[Show[Graphics[Circle[#,r5[k]]&/@Table[h3[k][[i]],{i,1,(k+1) (k 2-1),2}]],Graphics[Line[{{0,0},{0,1},{1,1},{1,0},{0,0}}]]],{{k,3,circle},2,7,1}]

A bemutatott minták nyilván nem fedik le az optimális körpakolásoknál előforduló összes lehetséges struktúrát. Az optimalizáló algoritmusok és a számítógépes hardver fejlődésével várhatóan egyre több optimális körpakolást fogunk megismerni, így nagyon valószínű, hogy a jövőben számos további mintaosztályt fognak feltárni a kutatók.

Hivatkozások

-Szabó Péter Gábor : Egybevágó körök pakolásai négyzetben - korlátok, ismétlődő minták és minimálpolinomok, Doktori értekezés, Szeged, 2005
-P. G. Szabó, M. Cs. Markót, T. Csendes, E. Sprecht, L. G. Casado, I. García: New approaches to circle packing in a square, 2007
-P. G. Szabó, T. Csendes, L. G. Casado, I. García: Packing Equal Circles in a Square I., 2000