Упаковка шаров

Размещение плодов апельсина

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

Упаковка кругов на плоскости

Наиболее эффективный способ упаковать круги разного размера не так уж очевиден

В двумерном Евклидовом пространстве наилучшим заполнением является размещение центров кругов в вершинах паркета, образованного правильными шестиугольниками, в котором каждый круг окружен шестью другими. Плотность данной упаковки

$\frac{\pi}{2\sqrt{3}} \approx 0.9069.$

Оптимальная упаковка кругов на плоскости

В 1940 году было доказано, что данная упаковка является самой плотной.

См. также

• Контактное число — сколько одинаковых шаров можно расположить вокруг одного такого же центрального шара, чтобы все они касались его.
• Задача о редчайшем покрытии — как наиболее экономно расположить одинаковые шары в пространстве, чтобы каждая точка пространства оказалась внутри или на границе хотя бы одного из них? (В отличие от задачи о плотнейшей упаковке (неперекрывающихся шаров), здесь шары обязательно перекрываются.)
• Алгоритм Любачевского — Стилинжера эвристически находит плотные упаковки шаров и кругов, причём эти упаковки часто оказываются оптимальными.
• Сингония
• Параллелоэдр

Ссылки

• Упаковка шаров
• Практическое применение упаковки шаров (на английском языке).
• Д. К. Новая головоломка: укладывание шариков в куб // Квант. — 1990. — № 5. — С. 82.