Pakke cirkler i en cirkel

Cirkel-i- cirkel -pakning er et 2D - pakningsproblem, hvis mål er at pakke enhedscirkler ind i den mindst mulige cirkel .

[en]

Historie

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] .

Tabel over de første 20 pakker

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]

Se også

Noter

  1. ↑ Erich Friedman, Circles in Circles on Erich's Packing Center (link ikke tilgængeligt) . Hentet 7. juni 2016. Arkiveret fra originalen 18. marts 2020. 
  2. ↑ Kravitz, 1967 .
  3. ↑ 1 2 3 Graham, 1968 .
  4. ↑ 1 2 3 4 Pirl, 1969 .
  5. ↑ 1 2 Melissen, 1994 .
  6. ↑ 12 Fodor, 2000 .
  7. ↑ 12 Fodor , 2003 .
  8. ↑ 12 Fodor , 1999 .
  9. ↑ 1 2 3 4 5 6 7 Graham, 1998 .
  10. ↑ Eckard Specht: De bedst kendte pakninger af lige store cirkler i en cirkel (komplet op til N = 2600). Arkiveret 4. marts 2016 på Wayback Machine packomania.com.

Litteratur


Links