球包装

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

问题是著名的是非常自然的，看似简单，但在严格意义上，即使方法非常困难。事实上，花了近400年，是在三维情况下，即使解决了这个问题，并通过使用大量的计算能力，这是唯一可能的;所得到的数据包括了三个字节。

球面填充在纠正代码纠错，使得近来特别重要的问题。

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

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

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

高斯的主要结果是橙色叠加法可能是最好的格包装，这意味着直觉，在一个非常规则的方式重复填料。然而，也有在某些情况下甚至最佳的晶格不包装，所以这并不能证明橙堆叠方法是最好的可能之中所有填料。

一种(非常)不规则的，但最理想的，将15个圆打包成一个正方形

下一个重大突破出现在1953年，当时拉兹洛·托特(Laszlo Toth)将这个问题简化为(非常)大量的具体案例。这意味着，就像四色定理，它是可以证明与使用专用计算机的定理。尽管如此，未来与执行计算的战略，采取了另外41年的时候海尔斯开发了一种算法，他花了四年执行。一个250页的论文和超过3 GB的数据后，开普勒猜想被最终证明。

最密堆积的问题来讲是最好的理解密度:相对于试图确定一个特定大小的盒子能容纳多少球体，更有趣的问题是有多少三维空间可以被球体填充(从体积上来说)。更正式,密度球面在有限空间中的填充是可以被球面填充的空间的一部分。正如上一节所示，当空间是特定大小时，这可能会导致奇怪的最佳瓦片，所以当考虑随着空间越来越大，密度如何变化时，更有趣的问题出现了;在正式意义上，目标是找到限制最佳的密度最密堆积的 $ñ\ n次\ n次$框， $n$趋向于无穷。

一个自然的策略是选择一个“小”的安排，并一遍又一遍地重复它，试图做类似的事情镶嵌细工的飞机．更正式,晶格排列(或定期安排)是一个球体的中心只需要 $n$完全定义的向量(在 $n$维的情况下;球形的情况下， $n = 3$）.这些排列是周期性的，也就是说它们是重复的。

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

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

这个问题的最简单的版本是减少到两个维度，其目的是平铺在最大化密度的这样一种方式圆面。

一个很自然的方法是安排在圆六角形模式,如图所示:

其中圆的中心基本上是用等边三角形镶嵌面。值得注意的是，这是一个格子结构的一个例子，因为它完全被载体所定义 $（0,1）$和 $\左（\压裂{1} {2}，\压裂{\ SQRT {3}} {2} \右）$(这意味着这些向量的任何线性组合都是圆心)。

计算这种排列的密度是相当简单的:因为所示的六边形能够镶嵌平面，所以圆圈所占的六边形的部分也是平面上圆圈的密度。这同样适用于由中心组成的等边三角形，它可能更容易分析。

六角圆布置的密度是

$\压裂{\ PI} {2 \ SQRT {3}} \约0.9069。$

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

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

令人惊讶的是，这也是一个非常难解决的问题，尽管对于哪种安排是最好的有着清晰的直觉。直到1940年，六边形瓷砖才被证明具有最大的密度，尽管早在1773年，它就被证明在所有格子瓷砖中具有最高的密度。

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

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

一个德劳内三角是其中在该组在于三角测量的三角形内没有意义的。

一个Delaunay三角不一定存在点的所有集合，它也不一定是唯一的。但是，在这种情况下，设定点的是一组在圆圈的中心最大最佳打包（并因此具有至少2的成对距离），这足以保证一个Delaunay三角存在。在这里，答：最大最佳打包意味着没有点可以被添加到该集合;否则，可以高密度化。

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

在最大圆填充的狄洛尼三角剖分中，最大角 $\θ$任意三角形满足

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

---

证明：因为三角形的内角和是 $\ PI.$时，左手不等式是显而易见的;最大的一组必须至少平均。

现在，假设 $\ THETA \ GEQ \压裂{2 \ PI} {3}$,让 $一个$是最小的角度。然后 $\罪罪< \ \压裂{\π}{3}= \压裂{1}{2}$,自 $公元前\眉题{}\组的2$， 这意味着 $公元前2 r = \压裂{}{罪\}\组\压裂{2}{\ \ \压裂{1}{2}\ \}= 4,$这意味着 $R \组2$．在这里 $R$是的外接圆 $美国广播公司$．

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

现在，考虑三角形的部分 $美国广播公司$它被圆圈占据。圆的 $一个$占用 $\π\ cdot \压裂{\角}{2 \π}= \压裂{1}{2}\角$区，类似的圆圈 $公元前$占 $\压裂{1} {2} \角B，\压裂{1} {2} \角度C$区域。所以三角形的密度

$\压裂{\压裂{1} {2} \角A + \压裂{1} {2} \角B + \压裂{1} {2} \角度C} {[ABC]} = \压裂{\压裂{\ PI} {2}} {[ABC]}。$

但 $(ABC) = \压裂{1}{2}\眉题{AB} \眉题公元前{}\罪\ B \组\压裂角{1}{2}\ cdot 2 \ cdot 2 \ cdot \压裂{\ sqrt {3}} {2} = \ sqrt {3}$，所以三角形的密度为至多 $\压裂{\ PI} {2 \ SQRT {3}}$．

然而，整个平面的密度为三角形的密度的加权和，其中每一个是至多 $\压裂{\ PI} {2 \ SQRT {3}}$．因此，整个平面的密度也至多 $\压裂{\ PI} {2 \ SQRT {3}}$．

此外，等式成立仅当 $公元前\眉题{AB} = \眉题{}= 2$和 $B = \ \角裂缝分析{\π}{3}$对于所有三角形，这意味着三角形中的每个三角形都是等边的。这意味着六边形晶格是理想的。

在3d的例子中，“自然”策略再次胜出，但要证明这一点要困难得多。这种自然策略的作用如下:

• 考虑与在其上的球体的布置的平面，配置成六方晶格（如在2-d的情况下）。
• 对于任何三个接触球体的集合，在三个球体之间的空间上方放置一个球体。在第一个平面以上重复这个“处处”，形成另一个球面。
• 在两个方向无限重复这个过程。

在第三步骤中，存在将要进行的选择：在层3上的球可被放置在相同的位置（但向上移动，很明显）作为球体在层1上，或者它们可以抵消略微使得在层的球体4将被放置在作为层1中的相同的位置（或2，潜在的）。这意味着，有球的三种不同的六角平面。If they are called A, B, and C, any sequence of As, Bs, and Cs such that no adjacent letters are the same (e.g. "ABCABC...", "ABCBABCBA...", etc.) will result in an analogously tightly-packed structure, and in fact all such packings are optimal.

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

最佳最密堆积的密度为

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

最近极端（如2016年），球体包装问题已经解决了在更高层面：8和24，这些看似随意的数字，但实际上他们都没有;正是这些尺寸允许究竟需要紧紧包额外的“橘子”到额外维度以这样的方式配合是额外的结构“从紧”。这听起来很暧昧，主要是因为它是;可视化在4种尺寸基本上是不可能的，更不用说24。

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

$0.0000000000000000000000000001 \$

这是一个非常紧约束。

最密堆积也高度与设计相关纠正代码纠错，如有半径的球体的中心 $t$对应于一个码字 $2T + 1$错误校正码。因此，有效的球填充可以用来发现有效的纠错码，而晶格球填充确实对应于线性码，而且 $G_ {} 24$(或格雷码)类似于24维的Leech晶格(如上所述，它最近被证明是最优的)。

• 平面的镶嵌