Упаковка кругов в круге (Rhgtkftg tjrikf f tjriy)

Перейти к навигации Перейти к поиску

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

[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 Тривиально оптимальна.
2 2 0.5000 Тривиально оптимальна.
3 ≈ 2.154... 0.6466... Тривиально оптимальна.
4 ≈ 2.414... 0.6864... Тривиально оптимальна.
5 ≈ 2.701... 0.6854... Тривиально оптимальна. Доказана оптимальность также Грэмом в 1968[3]
6 3 0.6667... Тривиально оптимальна. Доказана оптимальность также Грэмом в 1968[3]
7 3 0.7778... Тривиально оптимальна.
8 ≈ 3.304... 0.7328... Доказана оптимальность Пёрлом (Pirl) в 1969[4]
9 ≈ 3.613... 0.6895... Доказана оптимальность Пёрлом (Pirl) в 1969[4]
10 3.813... 0.6878... Доказана оптимальность Пёрлом (Pirl) в 1969[4]
11 ≈ 3.923... 0.7148... Доказана оптимальность Мелиссеном (Melissen) в 1994[5]
12 4.029... 0.7392... Доказана оптимальность Фодором (Fodor) в 2000[6]
13 ≈4.236... 0.7245... Доказана оптимальность Фодором (Fodor) в 2003[7]
14 4.328... 0.7474... Гипотетически оптимальна.[9]
15 ≈ 4.521... 0.7339... Гипотетически оптимальна.[9]
16 4.615... 0.7512... Гипотетически оптимальна.[9]
17 4.792... 0.7403... Гипотетически оптимальна.[9]
18 ≈ 4.863... 0.7611... Гипотетически оптимальна.[9]
19 ≈ 4.863... 0.8034... Доказана оптимальность Фодором (Fodor) в 1999[8]
20 5.122... 0.7623... Гипотетически оптимальна.[9]

Примечания

[править | править код]
  1. Erich Friedman, Circles in Circles on Erich's Packing Center. Дата обращения: 23 ноября 2023. Архивировано 16 марта 2023 года.
  2. Kravitz, 1967.
  3. 1 2 3 Graham, 1968.
  4. 1 2 3 4 Pirl, 1969.
  5. 1 2 Melissen, 1994.
  6. 1 2 Fodor, 2000.
  7. 1 2 Fodor, 2003.
  8. 1 2 Fodor, 1999.
  9. 1 2 3 4 5 6 7 Graham, 1998.
  10. Eckard Specht: The best known packings of equal circles in a circle (complete up to N = 2600). Архивная копия от 4 марта 2016 на Wayback Machine packomania.com.

Литература

[править | править код]
  • 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.