Упаковка кругов в круге

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Упаковка кругов в круге — это двумерная задача упаковки, целью которой является упаковка единичных кругов в как можно меньший круг.

[1]

История[править | править код]

Эта задача упаковки была поставлена и исследовалась в 60-х годах 20-го века. Кравиц в 1967 опубликовал упаковки до 19 кругов без анализа оптимальности решений[2]. Годом позже Грэм доказал, что найденные решения с числом кругов до 7 оптимальны[3], а Пёрл (Pirl), независимо от него, что оптимальны упаковки до 10 кругов[4]. Лишь в 1994 Мелиссеном (Melissen) была доказана оптимальность решения с 11 кругами[5]. Фодор (Fodor) показал между 1999 и 2003 годами, что решения с 12[6], 13[7] и 19[8]кругами оптимальны.

Грэм (Graham) и др. около 1998 предложили два алгоритма и нашли с помощью них упаковки до 65 кругов[9]. Последний обзор задачи и приближённых решений до 2989 кругов (июнь 2014) дал Экард Спехт (Eckard Specht)[10].

Таблица первых 20 упаковок[править | править код]

Минимальные решения (в случае существования нескольких минимальных решений показан только один вариант):

Число единичных кругов Радиус вмещающей окружности Плотность Оптимальность Диаграмма
1 1 1.0000 Тривиально оптимальна. Disk pack1.svg
2 2 0.5000 Тривиально оптимальна. Disk pack2.svg
3 ≈ 2.154... 0.6466... Тривиально оптимальна. Disk pack3.svg
4 ≈ 2.414... 0.6864... Тривиально оптимальна. Disk pack4.svg
5 ≈ 2.701... 0.6854... Тривиально оптимальна. Доказана оптимальность также Грэмом в 1968[3] Disk pack5.svg
6 3 0.6667... Тривиально оптимальна. Доказана оптимальность также Грэмом в 1968[3] Disk pack6.svg
7 3 0.7778... Тривиально оптимальна. Disk pack7.svg
8 ≈ 3.304... 0.7328... Доказана оптимальность Пёрлом (Pirl) в 1969[4] Disk pack8.svg
9 ≈ 3.613... 0.6895... Доказана оптимальность Пёрлом (Pirl) в 1969[4] Disk pack9.svg
10 3.813... 0.6878... Доказана оптимальность Пёрлом (Pirl) в 1969[4] Disk pack10.svg
11 ≈ 3.923... 0.7148... Доказана оптимальность Мелиссеном (Melissen) в 1994[5] Disk pack11.svg
12 4.029... 0.7392... Доказана оптимальность Фодором (Fodor) в 2000[6] Disk pack12.svg
13 ≈4.236... 0.7245... Доказана оптимальность Фодором (Fodor) в 2003[7] Disk pack13.svg Disk pack13b.svg
14 4.328... 0.7474... Гипотетически оптимальна.[9] Disk pack14.svg
15 ≈ 4.521... 0.7339... Гипотетически оптимальна.[9] Disk pack15.svg
16 4.615... 0.7512... Гипотетически оптимальна.[9] Disk pack16.svg
17 4.792... 0.7403... Гипотетически оптимальна.[9] Disk pack17.svg
18 ≈ 4.863... 0.7611... Гипотетически оптимальна.[9] Disk pack18.svg
19 ≈ 4.863... 0.8034... Доказана оптимальность Фодором (Fodor) в 1999[8] Disk pack19.svg
20 5.122... 0.7623... Гипотетически оптимальна.[9] Disk pack20.svg

См. также[править | править код]

Примечания[править | править код]

Литература[править | править код]

  • S. Kravitz. Packing cylinders into cylindrical containers // Math. Mag. — 1967. — Т. 40. — С. 65-71.
  • F. Fodor. The Densest Packing of 12 Congruent Circles in a Circle // Beiträge zur Algebra und Geometrie, Contributions to Algebra and Geometry. — 2000. — Т. 41. — С. 401–409.
  • F. Fodor. The Densest Packing of 13 Congruent Circles in a Circle // Beiträge zur Algebra und Geometrie, Contributions to Algebra and Geometry. — 2003. — Т. 44. — С. 431–440.
  • F. Fodor. The Densest Packing of 19 Congruent Circles in a Circle // Geom. Dedicata. — 1999. — Т. 74. — С. 139–145.
  • R.L. Graham. Sets of points with given minimum separation (Solution to Problem El921) // Amer. Math. Monthly. — 1968. — Т. 75. — С. 192-193.
  • R.L. Graham, B.D. Lubachevsky, K.J. Nurmela, P.R.J. Ostergard. Dense packings of congruent circles in a circle. // Discrete Math. — 1998. — С. 181:139–154.
  • U. Pirl. Der Mindestabstand von n in der Einheitskreisscheibe gelegenen Punkten // Mathematische Nachrichten. — 1969. — Т. 40. — С. 111-124.
  • H. Melissen. Densest packing of eleven congruent circles in a circle // Geometriae Dedicata. — 1994. — Т. 50. — С. 15-25.


Ссылки[править | править код]