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

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

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

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

Упаковка и выпуклые оболочки

Выпуклый корпус синего цвета

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

Формы упаковки

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

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

Упаковка колбасных изделий

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

Упаковка пиццы

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

Кластерная упаковка

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

Взаимосвязь между видами упаковки

Согласно данным определениям, любая колбасная упаковка технически является еще и упаковкой для пиццы, а любая упаковка для пиццы – технически еще и кластерной упаковкой. В более общем случае $d$ измерения, «колбаски» относятся к одномерным расположениям, «кластеры» — к $d$-мерные аранжировки и «пиццы» для тех, у кого есть промежуточное количество измерений.

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

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

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

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

Колбасная катастрофа

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

Внезапный переход к оптимальной форме упаковки некоторые математики в шутку называют колбасной катастрофой (Wills, 1985). обозначения Катастрофа происходит из-за того, что оптимальная форма упаковки внезапно меняется от упорядоченной упаковки колбасы к относительно неупорядоченной упаковке кластеров и наоборот при переходе от одного числа к другому, без удовлетворительного объяснения, почему это происходит. Несмотря на это, переход в три измерения относительно несложный; в $d=4$ Предполагается, что внезапный переход произойдет примерно в 377 000 сферах.

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

Пример неоптимальной упаковки колбасы

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

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

${\begin{aligned}V_{W}&=V_{\text{cylinder}}+2\cdot V_{\text{half-sphere}}\\&=V_{\text{cylinder}}+V_{\text{sphere}}\\&=\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}}$

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

$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}}$.

Теперь радиус $r$ тетраэдра с длиной стороны $a$ является

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

Из этого мы имеем

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

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

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

В случае, когда внутри тетраэдра расположено множество сфер, длина ребра $a$ увеличивает в два раза радиус сферы для каждого нового слоя, то есть для $x$ слоев длина стороны становится

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

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

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

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

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

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

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

Гипотеза о колбасе

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

Параметрическая плотность и родственные методы

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

Используемое ранее определение плотности касается объема выпуклой оболочки сфер (или выпуклых тел). $K$:

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

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

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

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

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

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

Имеет место неравенство:

${\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}$

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