Упаковка конечных сфер

В математике теория упаковки конечных сфер касается вопроса о том, как можно наиболее эффективно упаковать конечное число сфер одинакового размера . Вопрос упаковки конечного числа сфер был подробно исследован только в последние десятилетия, и большая часть фундамента была заложена Ласло Фейешем Тотом .

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

Задачи упаковки сфер различаются между упаковками в заданных контейнерах и свободными упаковками. В этой статье в первую очередь обсуждаются свободные упаковки.

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

Существует множество возможных способов размещения сфер, которые можно разделить на три основные группы: колбаса, пицца и кластерная упаковка. ^[1]

• 
  Упаковка колбасы
• 
  Упаковка пиццы
• 
  Кластерная упаковка

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

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

Если средние точки сфер расположены в трехмерном пространстве, упаковка называется кластерной упаковкой . Реальные приближения включают упаковку фруктов в несколько слоев в коробке.

Согласно данным определениям, любая упаковка колбасы технически является также упаковкой пиццы, а любая упаковка пиццы технически является также упаковкой кластера. В более общем случае измерений «колбасы» относятся к одномерным расположениям, «кластеры» к -мерным расположениям, а «пиццы» к тем, у которых есть промежуточное число измерений. ^[1]${\displaystyle д}$${\displaystyle д}$

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

Пустое пространство между сферами варьируется в зависимости от типа упаковки. Количество пустого пространства измеряется в плотности упаковки , которая определяется как отношение объема сфер к объему всей выпуклой оболочки. Чем выше плотность упаковки, тем меньше пустого пространства в упаковке и, следовательно, тем меньше объем оболочки (по сравнению с другими упаковками с тем же количеством и размером сфер).

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

При трех или четырех сферах упаковка колбасы является оптимальной. Считается, что это справедливо для любых вплоть до вместе с . ^{[1] [2]} Для и существует упаковка кластера, которая более эффективна, чем упаковка колбасы, как было показано в 1992 году Йоргом Виллсом и Пьером Марио Гандини. ^{[2] [3]} Остается неизвестным, как выглядят эти наиболее эффективные упаковки кластера. Например, в случае известно, что оптимальная упаковка не является тетраэдрической упаковкой, как классическая упаковка пушечных ядер, а, вероятно, имеет некую форму октаэдра . ^[1]${\displaystyle n}$${\displaystyle 55}$${\displaystyle n=57,58,63,64}$${\displaystyle n=56,59,60,61,62}$${\displaystyle n\geq 65}$${\displaystyle n=56}$

Внезапный переход в оптимальной упаковке в шутку известен некоторыми математиками как колбасная катастрофа (Уиллс, 1985). ^[4] Обозначение катастрофа происходит от того факта, что оптимальная упаковка внезапно переходит от упорядоченной колбасной упаковки к относительно неупорядоченной кластерной упаковке и наоборот при переходе от одного числа к другому, без удовлетворительного объяснения того, почему это происходит. Тем не менее, переход в трех измерениях относительно скромен; в измерениях внезапный переход предположительно происходит около 377000 сфер. ^[1]${\displaystyle d=4}$

Для измерений оптимальная упаковка всегда либо колбаса, либо кластер, и никогда пицца. Открытой проблемой является то, справедливо ли это для всех измерений. Этот результат касается только сфер, а не других выпуклых тел; фактически Грицман и Архельгер заметили, что для любого измерения существует выпуклая форма, для которой ближайшей упаковкой является пицца. ^[1]${\displaystyle d\leq 10}$${\displaystyle d\geq 3}$

В следующем разделе показано, что для 455 сфер упаковка «сосиски» неоптимальна, и что вместо этого существует специальная упаковка «кластер», которая занимает меньший объем.

Объем выпуклой оболочки упаковки сосисок со сферами радиуса можно вычислить с помощью элементарной геометрии. Средняя часть оболочки представляет собой цилиндр длиной , а крышки на концах — полусферы радиусом . Таким образом, общий объем определяется как.${\displaystyle n}$${\displaystyle r}$${\displaystyle h=2r\cdot (n-1)}$${\displaystyle r}$${\displaystyle V_{W}}$

${\displaystyle {\begin{aligned}V_{W}&=V_{\text{цилиндр}}+2\cdot V_{\text{полусфера}}\\&=V_{\text{цилиндр}}+V_{\text{сфера}}\\&=\pi hr^{2}+{\frac {4}{3}}\pi r^{3}\\&=\pi 2r\cdot (n-1)\cdot r^{2}+{\frac {4}{3}}\pi r^{3}\\&=2\cdot \left(n-{\frac {1}{3}}\right)\pi r^{3}\end{aligned}}}$

Аналогично можно найти объем выпуклой оболочки тетраэдрической упаковки, в которой сферы расположены так, что образуют тетраэдрическую форму, что приводит к полностью заполненным тетраэдрам только для определенного количества сфер. Если сферы расположены вдоль одного ребра тетраэдра, общее количество сфер определяется как${\displaystyle x}$${\displaystyle n}$

${\displaystyle n=\sum _{i=1}^{x}\sum _{j=1}^{i}j=\sum _{i=1}^{x}{\frac {i\cdot (i+1)}{2}}={\frac {x\cdot (x+1)\cdot (x+2)}{6}}}$.

Теперь радиус вписанной окружности тетраэдра со стороной длиной${\displaystyle r}$${\displaystyle а}$

${\displaystyle r={\frac {\sqrt {6}}{12}}\cdot a}$.

Из этого следует, что

${\displaystyle a=2{\sqrt {6}}\cdot r}$.

Объем тетраэдра тогда определяется по формуле${\displaystyle V_{T}}$

${\displaystyle V_{T}={\frac {\sqrt {2}}{12}}\cdot a^{3}={\sqrt {192}}\cdot r^{3}}$

В случае расположения множества сфер внутри тетраэдра длина ребра увеличивается на величину, вдвое превышающую радиус сферы для каждого нового слоя, что означает, что для слоев длина стороны становится${\displaystyle а}$${\displaystyle x}$

${\displaystyle a=2\cdot \left(x-1+{\sqrt {6}}\right)\cdot r}$.

Подставляя это значение в формулу объема тетраэдра, мы знаем, что объем выпуклой оболочки должен быть меньше самого тетраэдра, так что${\displaystyle V}$

${\displaystyle V<{\frac {2\cdot \left(x-1+{\sqrt {6}}\right)^{3}\cdot {\sqrt {2}}\cdot r^{3}}{3}}}$.

Беря число сфер в тетраэдре слоев и подставляя в предыдущее выражение, чтобы получить объем выпуклой оболочки упаковки сосисок с тем же числом сфер, имеем${\displaystyle n}$${\displaystyle V_{\text{W}}}$

${\displaystyle V_{\text{W}}={\frac {x\cdot (x+1)\cdot (x+2)-2}{3}}\cdot \pi r^{3}}$.

Для , что соответствует сферам, коэффициент перед равен примерно 2845 для тетраэдрической упаковки и 2856 для колбасной упаковки, что означает, что для этого количества сфер тетраэдр упакован более плотно.${\displaystyle x=13}$${\displaystyle n=455}$${\displaystyle r^{3}}$

Также возможно, приложив некоторые усилия, вывести точную формулу для объема тетраэдрической выпуклой оболочки , которая будет включать вычитание избыточного объема в углах и ребрах тетраэдра. Это позволяет доказать неоптимальность упаковки колбасы для меньших значений и, следовательно , .${\displaystyle V}$${\displaystyle x}$${\displaystyle n}$

Термин колбаса происходит от математика Ласло Фейеша Тота , который выдвинул гипотезу колбасы в 1975 году ^[5], которая касается обобщенной версии проблемы для сфер, выпуклых оболочек и объема в более высоких измерениях. Обобщенная сфера в измерениях - это -мерное тело, в котором каждая граничная точка лежит на одинаковом расстоянии от средней точки. Гипотеза колбасы Фейеша Тота затем утверждает, что сверху всегда оптимально располагать сферы вдоль прямой линии. То есть, катастрофа колбасы больше не происходит, как только мы поднимаемся выше 4 измерений. Общая гипотеза остается открытой. Лучшие результаты на данный момент получены Ульрихом Бетке и Мартином Хенком ^[6] , которые доказали гипотезу для измерений 42 и выше.${\displaystyle д}$${\displaystyle д}$${\displaystyle d=5}$

Хотя можно доказать, что упаковка колбасы не является оптимальной для 56 сфер, и что должна быть какая-то другая упаковка, которая является оптимальной, неизвестно, как выглядит оптимальная упаковка. Трудно найти оптимальную упаковку, поскольку не существует «простой» формулы для объема кластера произвольной формы. Оптимальность (и неоптимальность) показывается с помощью соответствующих оценок объема, используя методы из выпуклой геометрии , такие как неравенство Брунна-Минковского , смешанные объемы Минковского и формула Штейнера . Решающим шагом на пути к единой теории как конечных, так и бесконечных (решетчатых и нерешетчатых) упаковок сфер стало введение параметрических плотностей Йоргом Виллсом в 1992 году. Параметрическая плотность учитывает влияние краев упаковки. ^[7]

Определение плотности, использованное ранее, касается объема выпуклой оболочки сфер (или выпуклых тел) :${\displaystyle К}$

${\displaystyle \delta (K,C_{n})={\frac {nV(K)}{V(C_{n}+K)}}}$

где — выпуклая оболочка середин сфер ( вместо сферы можно взять и произвольное выпуклое тело для ). Для линейного расположения (колбаски) выпуклая оболочка — это отрезок прямой, проходящий через все середины сфер. Знак плюс в формуле относится к сложению множеств по Минковскому , так что относится к объему выпуклой оболочки сфер.${\displaystyle C_{n}}$${\displaystyle n}$${\displaystyle c_{i}}$${\displaystyle K_{i}}$${\displaystyle К}$${\displaystyle V(C_{n}+K)}$

Это определение работает в двух измерениях, где Ласло Фейес-Тот, Клод Роджерс и другие использовали его для формулировки единой теории конечных и бесконечных упаковок. В трех измерениях Уиллс приводит простой аргумент, что такая единая теория невозможна на основе этого определения: Самое плотное конечное расположение монет в трех измерениях — это колбаса с . Однако оптимальное бесконечное расположение — это шестиугольное расположение с , поэтому бесконечное значение не может быть получено как предел конечных значений. Чтобы решить эту проблему, Уиллс вводит модификацию определения, добавляя положительный параметр :${\displaystyle \дельта =1}$${\displaystyle \delta \приблизительно 0,9}$${\displaystyle \ро}$

${\displaystyle \delta (K,C_{n})={\frac {nV(K)}{V(C_{n}+\rho K)}}}$

${\displaystyle \rho }$позволяет учитывать влияние ребер (придавая выпуклой оболочке определенную толщину). Затем это сочетается с методами теории смешанных объемов и геометрии чисел Германа Минковского .

Для каждого измерения существуют значения параметров и такие, что для колбасы это самая плотная упаковка (для всех целых чисел ), а для и достаточно большого кластер является самым плотным. Эти параметры являются специфичными для измерения. В двух измерениях, так что происходит переход от колбас к кластерам (катастрофа колбасы).${\displaystyle d\geq 2}$${\displaystyle \rho _{s}(d)}$${\displaystyle \rho _{c}(d)}$${\displaystyle \rho \leq \rho _{s}(d)}$${\displaystyle n}$${\displaystyle \rho \geq \rho _{c}(d)}$${\displaystyle n}$${\displaystyle \rho _{c}(2)=\rho _{s}(2)={\frac {\sqrt {3}}{2}}}$

Имеет место неравенство: ^[7]

${\displaystyle {\frac {V(B^{d})}{2V(B^{d-1})}}{\rho _{c}(d)}^{1-d}\leq \delta (B^{d})\leq {\frac {V(B^{d})}{2V(B^{d-1})}}{\rho _{s}(d)}^{1-d}}$

где объем единичного шара в измерениях равен . Для , мы имеем и предсказывается, что это справедливо для всех измерений, в этом случае значение может быть найдено из значения .${\displaystyle B^{d}}$${\displaystyle d}$${\displaystyle V(B^{d})}$${\displaystyle d=2}$${\displaystyle \rho _{s}(d)=\rho _{c}(d)}$${\displaystyle \rho _{c}(d)}$${\displaystyle \delta (B^{d})}$