Empaquetado de círculos en un círculo
From Wikipedia, the free encyclopedia
El empaquetado de círculos en un círculo es un problema de empaquetado bidimensional, cuyo objetivo es alojar un conjunto de círculos iguales en el círculo más pequeño posible.
Si existe más de una solución óptima, se muestran todas.[1]
| Radio del círculo envolvente |
Densidad |
Solución | Disposición óptima de los círculos | |
|---|---|---|---|---|
| 1 | 1 | 1.0 | Trivialmente óptima. | |
| 2 | 2 | 0,5 | Trivialmente óptima. | |
| 3 | 2,155... |
0,6466... | Trivialmente óptima. | |
| 4 | 2,414... |
0,6864... | Trivialmente óptima. | |
| 5 | 2,701... |
0,6854... | Comprobada como óptima por Graham (1968).[2] |
|
| 6 | 3 | 0,6666... | Comprobada como óptima por Graham (1968).[2] |
|
| 7 | 3 | 0,7777... | Trivialmente óptima. | |
| 8 | 3,304... |
0,7328... | Comprobada como óptima por Pirl (1969).[3] |
|
| 9 | 3,613... |
0,6895... | Comprobada como óptima por Pirl (1969).[3] |
|
| 10 | 3,813... | 0,6878... | Comprobada como óptima por Pirl (1969).[3] |
|
| 11 | 3,923... |
0,7148... | Comprobada como óptima por Melissen (1994).[4] |
|
| 12 | 4,029... | 0,7392... | Comprobada como óptima por Fodor (2000).[5] |
|
| 13 | 4,236... |
0,7245... | Comprobada como óptima por Fodor (2003).[6] |
|
| 14 | 4,328... | 0,7474... | Comprobada como óptima por Ekanayake y LaFountain (2024).[7] |
|
| 15 | 4,521... |
0,7339... | Conjeturada como óptima por Pirl (1969).[8] |
|
| 16 | 4,615... | 0,7512... | Conjeturada como óptima por Goldberg (1971).[8] |
|
| 17 | 4,792... | 0,7403... | Conjeturada como óptima por Reis (1975).[8] |
|
| 18 | 4,863... |
0,7609... | Conjeturada como óptima por Pirl (1969), con ajustes adicionales de Graham, Lubachevsky, Nurmela y Östergård (1998).[8]. |
|
| 19 | 4,863... |
0,8032... | Comprobada como óptima por Fodor (1999).[9] |
|
| 20 | 5,122... | 0,7623... | Conjeturada como óptima por Goldberg (1971).[8] |
Casos especiales
Se considera que solo 26 empaquetamientos óptimos son rígidos (sin círculos capaces de vibrar, es decir, son configuraciones en las que no se puede mover ningún círculo sin alterar la solución resultante). Los números en negrita son primos:
- Comprobado para n = 1, 2, 3, 4, 5, 6, 7, 10, 11, 12, 13, 14, 19.
- Conjeturado para n = 15, 16, 17, 18, 22, 23, 27, 30, 31, 33, 37, 61, 91.
De estas, las soluciones para n = 2, 3, 4, 7, 19 y 37, alcanzan una densidad de empaquetamiento mayor que cualquier número menor y que sea mayor que 1 (todas las disposiciones con mayor densidad son rígidas).[10]