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 (${\displaystyle 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 ${\displaystyle R}$ és el radi del cercle gran i ${\displaystyle r}$ el radi dels cercles petits, la densitat d'empaquetament ve donada per:

${\displaystyle \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.^[1] Un any després, Graham va demostrar que eren òptimes les matrius trobades fins un màxim de 7 cercles,^[2] i Pirl (independentment d'ell) que les matrius fins un màxim de 10 cercles eren òptimes.^[3] No va ser fins al 1994 que Kreisen von Melissen va demostrar l’optimitat de la solució amb 11 cercles.^[4] Entre 1999 i 2003, Fodor va demostrar que les solucions amb 12,^[5] 13^[6] i 19 cercles^[7] 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.^[8] Eckard Specht ofereix solucions aproximades fins a 2989 cercles (a juny de 2014).^[9]

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:^[10]

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	${\displaystyle 1+{\frac {2}{\sqrt {3}}}}$ ≈ 2,154...	0,6466...	Trivialment òptim.
4	${\displaystyle 1+{\sqrt {2}}}$ ≈ 2,414...	0,6864...	Trivialment òptim.
5	${\displaystyle 1+{\sqrt {2\left(1+{\frac {1}{\sqrt {5}}}\right)}}}$ ≈ 2,701...	0,6854...	Trivialment òptim. Optimització demostrada per Graham (1968)[2]
6	3	0,6666...	Trivialment òptim. Optimització demostrada per Graham (1968)[2]
7	3	0,7777...	Trivialment òptim.
8	${\displaystyle 1+{\frac {1}{\sin \left({\frac {\pi }{7}}\right)}}}$ ≈ 3,304...	0,7328...	Optimització demostrada per Pirl (1969)[3]
9	${\displaystyle 1+{\sqrt {2\left(2+{\sqrt {2}}\right)}}}$ ≈ 3,613...	0,6895...	Optimització demostrada per Pirl (1969)[3]
10	3,813...	0,6878...	Optimització demostrada per Pirl (1969)[3]
11	${\displaystyle 1+{\frac {1}{\sin \left({\frac {\pi }{9}}\right)}}}$ ≈ 3,923...	0,7148...	Optimització demostrada per Melissen (1994)[4]
12	4,029...	0,7392...	Optimització demostrada per Fodor (2000)[5]
13	${\displaystyle 2+{\sqrt {5}}}$ ≈ 4,236...	0,7245...	Optimització demostrada per Fodor (2003)[6]
14	4,328...	0,7474...	Probablement òptim.[8]
15	${\displaystyle 1+{\sqrt {6+{\frac {2}{\sqrt {5}}}+4{\sqrt {1+{\frac {2}{\sqrt {5}}}}}}}}$ ≈ 4,521...	0,7339...	Probablement òptim.[8]
16	4,615...	0,7512...	Probablement òptim.[8]
17	4,792...	0,7403...	Probablement òptim.[8]
18	${\displaystyle 1+{\sqrt {2}}+{\sqrt {6}}}$ ≈ 4,863...	0,7611...	Probablement òptim.[8]
19	${\displaystyle 1+{\sqrt {2}}+{\sqrt {6}}}$ ≈ 4,863...	0,8034...	Optimització demostrada per Fodor (1999)[7]
20	5,122...	0,7623...	Probablement òptim.[8]

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

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

on ${\displaystyle 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 ${\displaystyle k}$ costats i de longitud lateral ${\displaystyle 2}$.

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

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

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

Referències

1. S. Kravitz, Packing cylinders into cylindrical containers, Math. Mag. 40 (1967), 65–71.
2. R.L. Graham, Sets of points with given minimum separation (Solution to Problem El921), Amer. Math. Monthly 75 (1968) 192-193.
3. U. Pirl, Der Mindestabstand von n in der Einheitskreisscheibe gelegenen Punkten, Mathematische Nachrichten 40 (1969) 111-124.
4. H. Melissen, Densest packing of eleven congruent circles in a circle, Geometriae Dedicata 50 (1994) 15-25.
5. F. Fodor, The Densest Packing of 12 Congruent Circles in a Circle, Beiträge zur Algebra und Geometrie, Contributions to Algebra and Geometry 41 (2000) ?, 401–409.
6. F. Fodor, The Densest Packing of 13 Congruent Circles in a Circle, Beiträge zur Algebra und Geometrie, Contributions to Algebra and Geometry 44 (2003) 2, 431–440.
7. F. Fodor, The Densest Packing of 19 Congruent Circles in a Circle, Geom. Dedicata 74 (1999), 139–145.
8. Graham RL, Lubachevsky BD, Nurmela KJ, Ostergard PRJ. Dense packings of congruent circles in a circle. Discrete Math 1998;181:139–154.
9. Eckard Specht: The best known packings of equal circles in a circle (complete up to N = 2600). packomania.com.
10. «Erich Friedman, Circles in Circles on Erich's Packing Center». Arxivat de l'original el 2020-03-18. [Consulta: 12 març 2020].

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.