Плотность упаковки или упаковки фракция из упаковки в некотором пространстве есть доля пространства , заполненные фигуры, составляющие упаковку. В задачах упаковки цель обычно состоит в том, чтобы получить упаковку максимально возможной плотности.
В компактных пространствах
Если K 1 ,…, K n - измеримые подмножества компактного пространства с мерой X и их внутренности попарно не пересекаются, то набор { K i } является упаковкой в X и его плотность упаковки равна
- .
В евклидовом пространстве
Если упаковываемое пространство бесконечно, например евклидово пространство , принято определять плотность как предел плотностей, проявляемых в шарах все большего и большего радиуса. Если B t - шар радиуса t с центром в начале координат, то плотность упаковки { K i : i ∈ℕ} равна
- .
Поскольку этот предел не всегда существует, также полезно определить верхнюю и нижнюю плотности как верхний предел и нижний предел вышеупомянутого соответственно. Если плотность существует, верхняя и нижняя плотности равны. При условии, что любой шар евклидова пространства пересекает только конечное число элементов упаковки и что диаметры элементов ограничены сверху, (верхняя, нижняя) плотность не зависит от выбора начала координат, а μ ( K i ∩ B t ) можно заменить на μ ( K i ) для любого элемента, который пересекает B t . [1] Шар также может быть заменен растяжением другого выпуклого тела, но в целом получаемые плотности не равны.
Оптимальная плотность упаковки
Часто интересуют упаковки, в которых могут использоваться только элементы определенного набора материалов. Например, набор снабжения может быть набором всех шаров заданного радиуса. Оптимальная плотность упаковки или постоянная упаковка , связанная с коллекцией питания является гранью верхних плотностей , полученных упаковками , которые являются подколлекцией коллекции питания. Если набор поставки состоит из выпуклых тел ограниченного диаметра, существует упаковка, плотность которой равна константе упаковки, и эта константа упаковки не меняется, если шары в определении плотности заменяются растяжениями какого-либо другого выпуклого тела. . [1]
Особым сбор питания интерес представляет все евклидовы движения по фиксированной выпуклого тела K . В этом случае мы называем постоянной упаковки упаковки константа K . Гипотеза Кеплера касается константы упаковки 3-шаров. Гипотеза Улама об упаковке утверждает, что 3-шары имеют самую низкую константу упаковки из всех выпуклых тел. Все переводы фиксированного тела также представляют интерес, и он определяет трансляционную константу упаковки этого тела.
Смотрите также
Рекомендации
- ^ Б Groemer, Х. (1986), "Некоторые основные свойство упаковки и покрытия константы", Дискретная и вычислительная геометрия , 1 (2): 183-193, DOI : 10.1007 / BF02187693