Empaquetament de cercles en un cercle

L'empaquetament de cercles en un cercle és un problema d’empaquetament bidimensional amb l’objectiu d’empaquetar un determinat nombre de cercles iguals dins d’un cercle unitat.

Problema

S'entén per «empaquetament de cercles en un cercle» la disposició no superposada d'un nombre predeterminat de cercles amb el mateix radi dins d'un cercle més gran. Hi ha dues preguntes pel problema de l'empaquetament:

• Com de grans poden ser els cercles més petits? Quants cercles ($n$) encaixen dins d'un cercle més gran amb un radi determinat?
• Quin és el radi del cercle gran si s'empaqueten cercles unitaris?

Per a ambdues preguntes, només és important la relació dels dos radis. Si $R$ és el radi del cercle gran i $r$ el radi dels cercles petits, la densitat d'empaquetament ve donada per:

$\eta ={\frac {nr^{2}}{R^{2}}}$.

Història

Aquest problema d'empaquetament es va plantejar i investigar per primera vegada a la dècada del 1960. Kravitz va publicar paquets amb fins a 19 cercles el 1967 sense considerar l’optimitat de les solucions. Un any després, Graham va demostrar que eren òptimes les matrius trobades fins un màxim de 7 cercles, i Pirl (independentment d'ell) que les matrius fins un màxim de 10 cercles eren òptimes. No va ser fins al 1994 que Kreisen von Melissen va demostrar l’optimitat de la solució amb 11 cercles. Entre 1999 i 2003, Fodor va demostrar que les solucions amb 12, 13 i 19 cercles són òptimes.

A més, també es coneixen solucions aproximades. Per exemple, el 1998. Graham et al. van declarar dos algorismes per crear paquets de fins a 65 cercles. Eckard Specht ofereix solucions aproximades fins a 2989 cercles (a juny de 2014).

Taula de les solucions dels primers 20 casos

S'han demostrat que existeixen diverses solucions mínimes, però només hi ha una variant a la següent taula:

Nombre de cercles unitaris interiors	Radi màxim del cercles interiors	Densitat d'empaquetament	Optimització	Diagrama
1	1	1,0000	Trivialment òptim.
2	2	0,5000	Trivialment òptim.
3	$1+{\frac {2}{\sqrt {3}}}$ ≈ 2,154...	0,6466...	Trivialment òptim.
4	$1+{\sqrt {2}}$ ≈ 2,414...	0,6864...	Trivialment òptim.
5	$1+{\sqrt {2\left(1+{\frac {1}{\sqrt {5}}}\right)}}$ ≈ 2,701...	0,6854...	Trivialment òptim. Optimització demostrada per Graham (1968)
6	3	0,6666...	Trivialment òptim. Optimització demostrada per Graham (1968)
7	3	0,7777...	Trivialment òptim.
8	$1+{\frac {1}{\sin \left({\frac {\pi }{7}}\right)}}$ ≈ 3,304...	0,7328...	Optimització demostrada per Pirl (1969)
9	$1+{\sqrt {2\left(2+{\sqrt {2}}\right)}}$ ≈ 3,613...	0,6895...	Optimització demostrada per Pirl (1969)
10	3,813...	0,6878...	Optimització demostrada per Pirl (1969)
11	$1+{\frac {1}{\sin \left({\frac {\pi }{9}}\right)}}$ ≈ 3,923...	0,7148...	Optimització demostrada per Melissen (1994)
12	4,029...	0,7392...	Optimització demostrada per Fodor (2000)
13	$2+{\sqrt {5}}$ ≈ 4,236...	0,7245...	Optimització demostrada per Fodor (2003)
14	4,328...	0,7474...	Probablement òptim.
15	$1+{\sqrt {6+{\frac {2}{\sqrt {5}}}+4{\sqrt {1+{\frac {2}{\sqrt {5}}}}}}}$ ≈ 4,521...	0,7339...	Probablement òptim.
16	4,615...	0,7512...	Probablement òptim.
17	4,792...	0,7403...	Probablement òptim.
18	$1+{\sqrt {2}}+{\sqrt {6}}$ ≈ 4,863...	0,7611...	Probablement òptim.
19	$1+{\sqrt {2}}+{\sqrt {6}}$ ≈ 4,863...	0,8034...	Optimització demostrada per Fodor (1999)
20	5,122...	0,7623...	Probablement òptim.

Si els cercles interiors formen un anell tancat (com passa amb els cercles 3, 4, 5, 6, 7, 8, 9, 11, 13, 18 i 19), la relació dels radis es dona com a

${\frac {R}{r}}=1+{\frac {1}{\sin({\tfrac {\pi }{k}})}}$,

on $k$ és el nombre de cercles d'aquest anell. La distància del centre d'aquests cercles amb el centre del cercle gran correspon al radi d'un polígon regular amb $k$ costats i de longitud lateral $2$.

En 12 cercles interiors, la proporció dels radis és implícitament igual a

${\frac {R}{r}}=1+{\frac {2}{{\sqrt {3}}x_{0}}}$,

on $x_{0}$ és el zero més petit del polinomi $9\,{x}^{5}\,-\,15\,x^{4}\,+\,7\,x^{3}\,-\,3x+1\,=\,0$

Bibliografia

• Pach, János; Brass, Peter; Moser, W. O. J. «Packing equal circles into squares, circles, spheres». A: Research problems in discrete geometry (en anglès). Springer Verlag, 2005, p. S. 28–43, bes. S. 30. 

Vegeu també

• Empaquetament de l'esfera d'Apol·loni
• Empaquetament d’esferes en una esfera
• Problema del recobriment d'un disc

Enllaços externs

• "The best known packings of equal circles in a circle (complete up to N = 2600)"
• "Online calculator for "How many circles can you get in order to minimize the waste?"
• Packomania for up to 2600 circles.