Плотность упаковки

Плотность упаковки в некотором пространстве — это доля пространства, заполненная упакованными телами (фигурами). В задачах упаковки обычно целью является получение упаковки с максимальной возможной плотностью.

Если K₁,…,K_n являются измеримыми подмножествами компактного в пространстве с мерой X и их множества внутренних точек попарно не пересекаются, то коллекция {K_i} является упаковкой в X и плотность этой упаковки равна

${\displaystyle \eta ={\frac {\sum _{i=1}^{n}\mu (K_{i})}{\mu (X)}}}$.

Если пространство, в которое осуществляется упаковка, бесконечно, как, например, евклидово пространство, плотность традиционно определяется как предел плотностей, получаемых упаковкой в шарах всё большего и большего размера. Если B_t — шар радиуса t с центром в начале координат, то плотность упаковки {K_i : i∈ℕ} равна

${\displaystyle \eta =\lim _{t\to \infty }{\frac {\sum _{i=1}^{\infty }\mu (K_{i}\cap B_{t})}{\mu (B_{t})}}}$.

Поскольку такой предел не всегда существует, полезно определить верхнюю и нижнюю плотности как верхний и нижний пределы. Если плотность существует, верхняя и нижняя плотности совпадают. Если обеспечено, что любой шар в евклидовом пространстве пересекает лишь конечное число элементов упаковки и если диаметры элементов ограничены сверху, верхняя и нижняя плотности не зависят от выбора начала координат и μ(K_i∩B_t) можно заменить на μ(K_i) для любого элемента, пересекающегося с B_t^[1]. Шары можно заменить на гомотетии некоторого другого выпуклого тела, но, в общем случае, полученные плотности могут отличаться.

Часто рассматривается упаковка с ограничением использования элементов некоторого набора элементов. Например, набор элементов может состоять из шаров определённого радиуса. Оптимальная плотность упаковки или константа упаковки, связанная с коллекцией, — это точная верхняя граница верхних плотностей, полученная упаковкой, содержащей подколлекцию набора элементов, из которых создаётся упаковка. Если заданная коллекция элементов для упаковки состоит из выпуклых тел ограниченного диаметра, существует упаковка, плотность которой равна константе упаковки, и эта константа упаковки не меняется, если шары в определении плотности заменить на гомотетии некоторого другого выпуклого тела^[1].

Представляют интерес все евклидовы движения^[англ.] фиксированного выпуклого тела K. В этом случае константу упаковки называют константой упаковки тела K. Гипотеза Кеплера касается константы упаковки трёхмерных шаров. Гипотеза Улама об упаковках^[англ.] утверждает, что трёхмерные шары имеют наименьшую константу упаковки по сравнению с другими выпуклыми телами. Все параллельные переносы фиксированного тела также представляют интерес, и для них вводится константа упаковки параллельного переноса тела.

• Атомный коэффициент упаковки^[англ.]
• Упаковка шаров

• Weisstein, Eric W. Packing Density (англ.) на сайте Wolfram MathWorld.