Körök pakolása körbe

A kör az egy körben csomagolás egy 2D -s csomagolási probléma , amelynek célja az egységkörök minél kisebb körbe történő becsomagolása .

[egy]

Történelem

Ezt a csomagolási problémát a 20. század 60-as éveiben határozták meg és tanulmányozták. Kravitz 1967-ben legfeljebb 19 körből álló csomagokat publikált anélkül, hogy a megoldások optimálisságát elemezte volna [2] . Egy évvel később Graham bebizonyította, hogy a 7-ig terjedő körszámmal talált megoldások az optimálisak [3] , Pirl pedig tőle függetlenül, hogy 10 körig az optimális [4] . Melissen csak 1994-ben bizonyította 11 körrel a megoldás optimálisságát [5] . Fodor 1999 és 2003 között kimutatta, hogy a 12 [6] , 13 [7] és 19 [8] körből álló megoldások az optimálisak.

Graham és munkatársai 1998 körül két algoritmust javasoltak, és ezek segítségével találtak legfeljebb 65 körből álló tömítéseket [9] . A probléma utolsó áttekintését és hozzávetőleges megoldásait 2989 körig (2014. június) Eckard Specht adta [10] .

Az első 20 csomag táblázata

Minimális megoldások (ha több minimális megoldás van, csak egy lehetőség jelenik meg):

Az egységkörök száma	A befoglaló kör sugara	Sűrűség	Optimalitás	Diagram
egy	egy	1.0000	Triviálisan optimális.
2	2	0,5000	Triviálisan optimális.
3	≈ 2,154...	0,6466...	Triviálisan optimális.
négy	≈ 2,414...	0,6864...	Triviálisan optimális.
5	≈ 2,701...	0,6854...	Triviálisan optimális. Az optimalitást Graham is bebizonyította 1968-ban [3]
6	3	0,6667...	Triviálisan optimális. Az optimalitást Graham is bebizonyította 1968-ban [3]
7	3	0,7778...	Triviálisan optimális.
nyolc	≈ 3,304...	0,7328...	Pirl 1969-ben bizonyította az optimálisságot [4]
9	≈ 3,613...	0,6895...	Pirl 1969-ben bizonyította az optimálisságot [4]
tíz	3,813...	0,6878...	Pirl 1969-ben bizonyította az optimálisságot [4]
tizenegy	≈ 3,923...	0,7148...	Az optimalitást Melissen 1994-ben bizonyította [5]
12	4,029...	0,7392...	Fodor által 2000-ben bizonyított optimalitás [6]
13	≈4,236...	0,7245...	Fodor által 2003-ban bizonyított optimalitás [7]
tizennégy	4.328...	0,7474...	hipotetikusan optimális. [9]
tizenöt	≈ 4,521...	0,7339...	hipotetikusan optimális. [9]
16	4,615...	0,7512...	hipotetikusan optimális. [9]
17	4,792...	0,7403...	hipotetikusan optimális. [9]
tizennyolc	≈ 4,863...	0,7611...	hipotetikusan optimális. [9]
19	≈ 4,863...	0,8034...	Az optimalitást Fodor 1999-ben bizonyította [8]
húsz	5.122...	0,7623...	hipotetikusan optimális. [9]

Lásd még

• Lemezlefedettségi probléma

Jegyzetek

1. ↑ Erich Friedman, Körök a körökben az Erich csomagolóközpontjában (a link nem érhető el) . Letöltve: 2016. június 7. Az eredetiből archiválva : 2020. március 18. (határozatlan) 
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: A körben lévő egyenlő körök legismertebb tömítései (teljesítsd N = 2600-ig). Archiválva : 2016. március 4. a Wayback Machine packomania.com webhelyen.

Irodalom

• S. Kravitz. Hengerek csomagolása hengeres tartályokba  // Math. Mag. - 1967. - T. 40 . - S. 65-71 .
• F. Fodor. A 12 egybevágó kör legsűrűbb összecsomagolása egy körben // Beiträge zur Algebra und Geometry, Hozzájárulások az algebrához és a geometriához. - 2000. - T. 41 . – S. 401–409 .
• F. Fodor. A 13 egybevágó kör legsűrűbb csomagolása egy körben // Beiträge zur Algebra und Geometry, Hozzájárulások az algebrához és a geometriához. - 2003. - T. 44 . — S. 431–440 .
• F. Fodor. A 19 egybevágó kör legsűrűbb csomagolása egy körben // Geom. Dedicata. - 1999. - T. 74 . – S. 139–145 .
• RL Graham. Ponthalmazok adott minimális távolsággal (El921 probléma megoldása)  // Amer. Math. Havi. - 1968. - T. 75 . - S. 192-193 .
• RL Graham, BD Lubachevsky, KJ Nurmela, PRJ Ostergard. Egybevágó körök sűrű csomagolása egy körben. // Diszkrét matematika. - 1998. - S. 181: 139-154 .
• U. Pearl. Der Mindestabstand von n in der Einheitskreisscheibe gelegenen Punkten // Mathematische Nachrichten . - 1969. - T. 40 . - S. 111-124 .
• H. Melissen. Tizenegy egybevágó körből álló legsűrűbb tömörítés egy körben // Geometriae Dedicata . - 1994. - T. 50 . - S. 15-25 .

Linkek

• "A körben lévő egyenlő körök legismertebb pakolásai (teljesítsd N = 2600-ig)"
• "Online kalkulátor a "Hány kört kaphat a hulladék minimalizálása érdekében?"
• Packomania akár 2600 körhöz.