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

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

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

В компактных пространствах[править | править код]

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

.

В евклидовом пространстве[править | править код]

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

.

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

Оптимальная плотность упаковки[править | править код]

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

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

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

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

  1. 1 2 Groemer, 1986, с. 183.

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

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