Piirien pakkaaminen ympyrään

Ympyrä- ympyräpakkaus on 2D - pakkausongelma , jonka tavoitteena on pakata yksikköympyrät mahdollisimman pieneen ympyrään .

[yksi]

Historia

Tämä pakkausongelma asetettiin ja sitä tutkittiin 1900-luvun 60-luvulla. Kravitz julkaisi vuonna 1967 jopa 19 ympyrän pakkauksia analysoimatta ratkaisujen optimaalisuutta [2] . Vuotta myöhemmin Graham osoitti, että löydetyt ratkaisut, joissa on enintään 7 ympyrää, ovat optimaalisia [3] ja Pirl, hänestä riippumatta, että jopa 10 ympyrän tiivistykset ovat optimaalisia [4] . Vasta vuonna 1994 Melissen osoitti optimaalisen ratkaisun 11 ympyrällä [5] . Fodor osoitti vuosina 1999-2003, että ratkaisut, joissa on 12 [6] , 13 [7] ja 19 [8] ympyrää, ovat optimaalisia.

Graham ym. ehdottivat kahta algoritmia noin vuonna 1998 ja käyttivät niitä jopa 65 ympyrän tiivisteiden löytämiseen [9] . Eckard Specht antoi viimeisen katsauksen ongelmasta ja likimääräisistä ratkaisuista 2989 ympyrään saakka (kesäkuu 2014 ) .

Taulukko ensimmäisistä 20 pakkauksesta

Minimiratkaisut (jos minimiratkaisuja on useita, näytetään vain yksi vaihtoehto):

Yksikköympyröiden lukumäärä Ympyrän säde Tiheys Optimaalisuus Kaavio
yksi yksi 1.0000 Triviaalisti optimaalinen.
2 2 0,5000 Triviaalisti optimaalinen.
3 ≈ 2,154... 0,6466... Triviaalisti optimaalinen.
neljä ≈ 2,414... 0,6864... Triviaalisti optimaalinen.
5 ≈ 2,701... 0,6854... Triviaalisti optimaalinen. Optimaalisuuden todisti myös Graham vuonna 1968 [3]
6 3 0,6667... Triviaalisti optimaalinen. Optimaalisuuden todisti myös Graham vuonna 1968 [3]
7 3 0,7778... Triviaalisti optimaalinen.
kahdeksan ≈ 3,304... 0,7328... Pirl osoitti optimaalisuuden vuonna 1969 [4]
9 ≈ 3,613... 0,6895... Pirl osoitti optimaalisuuden vuonna 1969 [4]
kymmenen 3,813... 0,6878... Pirl osoitti optimaalisuuden vuonna 1969 [4]
yksitoista ≈ 3,923... 0,7148... Optimaalisuuden todisti Melissen vuonna 1994 [5]
12 4.029... 0,7392... Fodorin vuonna 2000 osoittama optimaalisuus [6]
13 ≈4,236... 0,7245... Fodorin todentama optimaalisuus vuonna 2003 [7]
neljätoista 4.328... 0,7474... hypoteettisesti optimaalinen. [9]
viisitoista ≈ 4,521... 0,7339... hypoteettisesti optimaalinen. [9]
16 4,615... 0,7512... hypoteettisesti optimaalinen. [9]
17 4,792... 0,7403... hypoteettisesti optimaalinen. [9]
kahdeksantoista ≈ 4,863... 0,7611... hypoteettisesti optimaalinen. [9]
19 ≈ 4,863... 0,8034... Optimaalisuuden todisti Fodor vuonna 1999 [8]
kaksikymmentä 5.122... 0,7623... hypoteettisesti optimaalinen. [9]

Katso myös

Muistiinpanot

  1. ↑ Erich Friedman, Circles in Circles on Erich's Packing Center (linkki ei ole käytettävissä) . Haettu 7. kesäkuuta 2016. Arkistoitu alkuperäisestä 18. maaliskuuta 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: Tunnetuimmat yhtäläisten ympyröiden pakkaukset ympyrässä (täydellinen N = 2600 asti). Arkistoitu 4. maaliskuuta 2016 osoitteessa Wayback Machine packomania.com.

Kirjallisuus


Linkit