Cirkel-i- cirkel -pakning er et 2D - pakningsproblem, hvis mål er at pakke enhedscirkler ind i den mindst mulige cirkel .
Dette pakkeproblem blev sat og undersøgt i 60'erne af det 20. århundrede. Kravitz udgav i 1967 pakninger med op til 19 cirkler uden at analysere optimaliteten af løsninger [2] . Et år senere beviste Graham , at de fundne løsninger med antallet af cirkler op til 7 er optimale [3] , og Pirl, uafhængigt af ham, at pakninger op til 10 cirkler er optimale [4] . Det var først i 1994, at Melissen beviste optimaliteten af en løsning med 11 cirkler [5] . Fodor viste mellem 1999 og 2003, at løsninger med 12 [6] , 13 [7] og 19 [8] cirkler er optimale.
Graham et al. foreslog to algoritmer omkring 1998 og brugte dem til at finde pakninger på op til 65 cirkler [9] . Den sidste gennemgang af problemet og omtrentlige løsninger op til 2989 cirkler (juni 2014) blev givet af Eckard Specht [10] .
Minimalløsninger (hvis der er flere minimale løsninger, vises kun én mulighed):
Antal enhedscirkler | Radius af den omsluttende cirkel | Massefylde | Optimalitet | Diagram |
---|---|---|---|---|
en | en | 1.0000 | Trivielt optimalt. | |
2 | 2 | 0,5000 | Trivielt optimalt. | |
3 | ≈ 2.154... | 0,6466... | Trivielt optimalt. | |
fire | ≈ 2.414... | 0,6864... | Trivielt optimalt. | |
5 | ≈ 2.701... | 0,6854... | Trivielt optimalt. Optimalitet blev også bevist af Graham i 1968 [3] | |
6 | 3 | 0,6667... | Trivielt optimalt. Optimalitet blev også bevist af Graham i 1968 [3] | |
7 | 3 | 0,7778... | Trivielt optimalt. | |
otte | ≈ 3.304... | 0,7328... | Beviste optimalitet af Pirl i 1969 [4] | |
9 | ≈ 3.613... | 0,6895... | Beviste optimalitet af Pirl i 1969 [4] | |
ti | 3.813... | 0,6878... | Beviste optimalitet af Pirl i 1969 [4] | |
elleve | ≈ 3.923... | 0,7148... | Optimalitet blev bevist af Melissen i 1994 [5] | |
12 | 4.029... | 0,7392... | Bevist optimalitet af Fodor i 2000 [6] | |
13 | ≈4.236... | 0,7245... | Dokumenteret optimalitet af Fodor i 2003 [7] | |
fjorten | 4.328... | 0,7474... | hypotetisk optimal. [9] | |
femten | ≈ 4.521... | 0,7339... | hypotetisk optimal. [9] | |
16 | 4.615... | 0,7512... | hypotetisk optimal. [9] | |
17 | 4.792... | 0,7403... | hypotetisk optimal. [9] | |
atten | ≈ 4.863... | 0,7611... | hypotetisk optimal. [9] | |
19 | ≈ 4.863... | 0,8034... | Optimalitet blev bevist af Fodor i 1999 [8] | |
tyve | 5.122... | 0,7623... | hypotetisk optimal. [9] |
Emballeringsopgaver | |
---|---|
Pakke cirkler |
|
Ballonpakning |
|
Andre pakker | |
Gåde |