球包装

球包装是在一定空间内排列不重叠球体的问题，其目标是使球体的组合体积最大化。在经典的情况下，所有的球体都是相同的大小，所讨论的空间是三维空间(例如一个盒子)，但这个问题可以扩展到考虑不同大小的球体，更高(或更低)维度，或不同类型的形状(例如四面体)。

这个问题以非常自然和看似简单而闻名，但在严格意义上很难接近。事实上，即使是在三维情况下，这个问题也花了近400年的时间来解决，而这只能通过使用强大的计算能力来实现;生成的数据超过3g字节。

球形填料具有惊人的应用纠错码这使得这个问题在近期尤为重要。

球形包装的问题在日常生活中非常明显;例如，许多杂货店把水果(尤其是橙子)堆成金字塔形，说明了可能的球形包装。

事实上，这个问题的起源非常相似:沃尔特·罗利爵士(Sir Walter Raleigh)在一次探险中问他的一位数学家朋友，他船上的炮弹最有效的堆放方式是什么。这位数学家意识到他无法回答这个问题，就把这个问题交给了约翰内斯·开普勒(Johannes Kepler)天文学研究)．

开普勒推测，“明显的”包装——橙色堆叠法——实际上是最好的可能，并通过将其与其他一些基本策略进行比较来支持这一观点。然而，解决这个问题被证明是困难的，直到高斯才取得重大进展。

高斯的主要结果是橙色堆叠法是其中最好的方法格包装，直观地说，是指以高度规则的方式重复的包装。然而，在某些情况下，也有非晶格包装是最优的，所以这并不能证明橙色堆叠方法是其中最好的所有包装。

一个(非常)不规则的，但最优的，将15个圆包装成一个正方形

下一个重大突破发生在1953年，拉兹洛·托特(Laszlo Toth)将问题简化为(非常)大量的具体案例。这意味着，就像四色定理在美国，专门使用计算机来证明这个定理是可能的。尽管如此，黑尔斯又花了41年才想出执行计算的策略，他开发了一种算法，又花了4年时间执行。在一篇250页的论文和超过3gb的数据之后，开普勒的猜想终于被证明了。

球体堆积的问题最好理解为密度:与其试图确定一个特定大小的盒子能装下多少个球体，更有趣的问题是有多少三维空间可以被球体填满(就体积而言)。更正式的说法是密度在有限空间中，一个球体的体积是可以被球体填满的那部分空间。正如上一节所示，当空间具有特定大小时，这可能会导致奇怪的最佳倾斜，所以当考虑密度如何随着空间越来越大而变化时，更有趣的问题就出现了;在正式意义上，目标是找到限制的最佳球填料密度 $N \乘N \乘N$箱, $n$趋于无穷。

一个自然的策略是选择一个“小”的安排，并一遍又一遍地重复，试图做一些类似的事情对平面进行镶嵌．更正式的说法是晶格排列(或定期安排)是一个球体的中心只需要 $n$方法中完全定义的向量 $n$维;在球体的例子中， $n = 3$)．这些安排是周期性的，也就是说它们是重复的。

一个不规则的安排是球体的中心不形成晶格的一种;在某种意义上，它们似乎是“随机”分布的。

因为对称还有规律性，晶格排列比不规则排列更容易分析。然而，特别是由于不规则排列在某些小情况下是最优的，因此不能立即排除在极限情况下是最优的可能性。

这个问题最简单的版本是缩减到二维，其目标是在平面上平铺圆，以使密度最大化。

一种非常自然的方法是将圆圈排列在六角模式，如图所示:

这些圆的圆心实际上是用等边三角形来镶嵌平面。值得注意的是，这是一个晶格排列的例子，因为它完全由向量定义 $(0,1)$而且 $\离开(\压裂{1}{2},\压裂{\ sqrt{3}}{2} \右)$(这意味着这些向量的任何线性组合都是圆心)。

计算这种排列的密度是相当直接的:由于所示的六边形能够将平面镶嵌，因此这些圆所占的六边形的部分也是平面中圆的密度。由圆心组成的等边三角形也是如此，这可能更容易分析。

六角圆排列的密度为

$\frac{\pi}{2\sqrt{3}} \约0.9069。$

有趣的是，与其他形状相比，这个数字很低;例如，五边形，它没有镶嵌平面，至少有一个填充密度 $\frac{5-\sqrt{5}}{3} \约0.9213$:然而，它并不是平铺平面的“最差”形状。虽然确切的最糟糕的形状还不知道，但平滑的八边形被推测是最糟糕的:平滑的八边形是用双曲线的一部分代替每个角而形成的

密度为 $\压裂大概{2}- {8 - 4 \ \ ln{2}}{2 \√{2}1}\约0.9024。$

令人惊讶的是，这也是一个非常难以解决的问题，尽管有明确的直觉哪种安排是最好的。直到1940年，六角形瓦片才被证明密度最大，尽管早在1773年，六角形瓦片就被证明是所有格子瓦片中密度最高的。

证明六角形平铺是最优的需要一些定义，但在原则上并不困难。给定平面上的一组点，a三角测量一组三角形是这样的吗

• 每对三角形相交于一个点，一条边，或者根本不相交;
• 三角形的顶点正好构成了原始的点集。

一个德劳内三角在三角剖分中，集合中没有点在三角形内。

德劳内三角剖分并不一定存在于所有的点集，也不一定是唯一的。但在这种情况下，点的集合就是a中圆心的集合最大最优的包装(因此至少有2对距离)，这足以保证德劳内三角测量的存在。在这里,一个最大最优包装意味着没有点可以添加到集合中;否则，密度会增加。

Delauney三角测量，来自https://en.wikipedia.org/wiki/Delaunay三角测量

在德劳内三角剖分的最大圆填充中，最大的角度 $\θ$任意三角形都满足

$\frac{\pi}{3} \leq \theta < \frac{2\pi}{3}。$

---

证明:因为三角形的内角和为 $\π$，左不等式明显;一个集合的最大值必须至少是它的平均值。

现在,假设 $\theta \geq \frac{2\pi}{3}$，让 $一个$是最小的角。然后 $\罪罪< \ \压裂{\π}{3}= \压裂{1}{2}$，自从 $\overline{BC} \geq 2$，这意味着 $公元前2 r = \压裂{}{罪\}\组\压裂{2}{\ \ \压裂{1}{2}\ \}= 4,$这意味着 $R \geq 2$．在这里 $R$的圆周半径是多少 $美国广播公司$．

然而，这意味着周心 $O$的 $美国广播公司$可以添加到集合中，与它的最大值相矛盾。所以, $θ< \ \压裂{2 \π}{3}$根据需要。 $_ \广场$

现在，考虑三角形的部分 $美国广播公司$它被圆占据了。这个圆在 $一个$占用 $\π\ cdot \压裂{\角}{2 \π}= \压裂{1}{2}\角$面积，类似的圆在 $B, C$拿起 $\frac{1}{2}\角度B， \frac{1}{2}\角度C$区域。所以三角形的密度是

$\压裂{\压裂{1}{2}\角+ \压裂{1}{2}\ B +角\压裂{1}{2}\角C} {(ABC)} = \压裂{\压裂{\π}{2}}{(ABC)}。$

但 $(ABC) = \压裂{1}{2}\眉题{AB} \眉题公元前{}\罪\ B \组\压裂角{1}{2}\ cdot 2 \ cdot 2 \ cdot \压裂{\ sqrt {3}} {2} = \ sqrt {3}$，则三角形的密度最大 $\压裂{\π}{2 \√{3}}$．

然而，整个平面的密度是三角形密度的加权和，每个三角形的密度都是最大的 $\压裂{\π}{2 \√{3}}$．因此整个平面的密度也是最大的 $\压裂{\π}{2 \√{3}}$．

此外，平等只有在 $公元前\眉题{AB} = \眉题{}= 2$而且 $B = \ \角裂缝分析{\π}{3}$对于所有三角形，也就是说三角剖分中的每个三角形都是等边的。这意味着六边形晶格是理想的。

在3d的情况下，“自然”策略再次胜出，但它明显更难证明。这种自然策略的工作原理如下:

• 考虑一个平面，上面有球体排列，排列成六角形晶格(就像二维的情况一样)。
• 对于任何三个接触球的集合，在三个球之间的空间上放置一个球。在第一个平面上方的“所有地方”重复这个步骤，形成另一个球体平面。
• 在两个方向上无限重复这个过程。

在第三步，需要做出选择:第3层上的球体可以被放置在与第1层上的球体相同的位置(但显然要向上移动)，或者它们可以稍微偏移，以便第4层上的球体将被放置在与第1层(或第2层)相同的位置。这意味着球体有三个不同的六角形平面。如果它们被称为A、B和C，则A、B和C的任意序列，使得相邻的字母都不相同(如A、B和C)。"ABCABC…"，"ABCBABCBA…"，等等)将导致类似的紧密包装结构，事实上所有这样的包装都是最优的。

同样，密度并不太难计算，但第三维使其更难以可视化。直观地说，三维平面的密度与边长为2的四面体的密度相同，四面体的四个顶点都是半径为1的球体。该密度如下:

最佳球填料的密度为

$3 \ \压裂{\π}{sqrt{2}}。$

最近(截至2016年)，球面填充问题已经在更高的维度(8维和24维)中得到解决。这些数字看似随意，但实际上并非如此;正是这些维度允许以“紧密”的方式将额外的“橙子”紧密地打包到额外的维度中所需的额外结构。这听起来模棱两可，很大程度上是因为事实就是如此;4维的可视化基本上是不可能的，更不用说24维了。

有趣的是，这一结果改进了先前的估计，即最好的球形填料最多 $10 ^ {-25}$比最著名的边界还要密集。也就是说，最著名的包装中的错误最多

$0.0000000000000000000000000001 \$

这是一个非常紧密的界限。

球形包装也与设计高度相关纠错码，即有半径的圆心 $t$对应于a的码字 $2 t + 1$错误修正代码。因此，可以利用有效的球面填充来发现有效的纠错码，实际上晶格球面填充对应于线性码，以及 $G_ {24}$(或戈利代码)类似于24维的Leech晶格(如上所述，最近被证明是最优的)。

• 平面的镶嵌