4.1 多面体
(Polyhedra)

4.1.1. 简介(Introduction)

多面体是二维多边形在三维空间中的自然推广。它是一个由有限个平面多边形面(face)构成的空间区域，任意两个面要么不相交，要么在边(edges)和顶点(vertices)处相交。 这个描述比较模糊，而要精准地描述这一概念，是一项出人意料的精细工作。本章我们主要关注的是凸多面体(它比一般多面体更简单)，我们本可以避免对多面体给出精确定义。 但直面这些困难，有助于培养三维几何直觉(three-dimensional geometric intuition) —— 这是理解计算几何的一项宝贵技能。

现在我们来准确描述多面体的边界或表面。它由三类几何对象构成: 零维的顶点(点)、一维的边(线段)和二维的面(多边形)。 为了简化问题，我们要求面为凸多边形，并定义其为有界多边形(1.1.1 节)。 这并不会损失一般性，因为任何非凸面都可以被划分为多个凸面，只是这样我们必须允许相邻的多边形可以共面。 有效的多面体表面可以通过各组成部分之间的关系来定义。我们采用三种类型的关系: 各组成部分"正确地"相交、局部拓扑"正确"以及全局拓扑"正确"。现在，我们将详细阐述这些约束条件。

1. 组成部分正确相交(Components intersect "properly")

   对于每一对面，我们要求其满足以下任一情况：
   (a) 它们互不相交；或
   (b) 它们有一个公共顶点；或
   (c) 它们有两个公共顶点，并且连接这两个顶点的边也相同。

   这里，假设面是凸面，简化了条件。非正常相交不仅包括穿透面，还包括以"错误"方式接触的面，参见图 4.1。 我们无需指定边和顶点相交的条件，因为面的条件也涵盖了它们。因此，一对边的非正常相交意味着一对面的非正常相交。



2. 局部拓扑正确(Local topology is "proper")

   局部拓扑是指曲面在某一点附近的拓扑结构。可以通过邻域neighborhoods的概念精确描述它。所谓邻域是指，曲面上围绕某一点的任意小的开放区域。 我们试图排除图 4.2 中所示的三个对象。图中所有三个示例中，都存在一些点，它们的邻域拓扑并非二维圆盘。 为了更好地表达这一约束，我们要求曲面上每个点的邻域都"同胚 homeomorphic"于一个圆盘。两个区域之间的同胚允许拉伸和弯曲，但不允许撕裂。 如果一只苍蝇在曲面上飞行，它会发现每个点的邻域在拓扑上都类似于一个圆盘。对于每个点都满足这一条件的曲面称为二维流形 2-manifold，这是一个比多面体边界更一般的类。

   我们已经从几何角度表达了这一条件，但从组合角度来看待它也很有用。假设我们对多边形面进行三角分割。那么每个顶点都是若干个三角形的顶点。 定义顶点 \(v\) 的环link为所有与 \(v\) 关联的三角形中，与 \(v\) 相对的边的集合。 因此，环在某种意义上是 \(v\) 的组合邻域。对于一个合法的三角分割多面体，我们要求每个顶点的环都是一条简单的闭合多边形路径。 例如，图 4.2(b) 中带圆圈的顶点的链环就不是这样的路径。

   这个条件的一个推论是，每条边恰好被两个面共享。

3. 全局拓扑正确(Global topology is "proper")

   我们希望曲面是连通的、封闭的且有界的。因此，我们要求曲面是连通的，即从曲面上任意一点出发，都可以到达曲面上的其他任意一点。 通过组合学的方式来表述，就是要求曲面具有 1-骨架(1-skeleton)，即边和顶点构成的图是连通的。注意，诸如带有"悬浮"的内部立方体空腔的立方体，这样的几何体就不满足条件。 结合之前对有限个面的规定，我们之前的条件已经蕴含了曲面的封闭性和有界性，尽管这可能并非显而易见(参见练习 4.1.6[1])。

   人们或许会倾向于在多面体的定义中排除"孔洞"，所谓的孔洞是指从表面一侧通向另一侧的"通道channel"，与空腔(cavity)不同，它们并非与外部不连通(do not disconnect the exterior)。 那么，环面(类似甜甜圈的形状)是否应该被视为多面体呢？我们按照惯例，允许多面体拥有任意数量的此类孔洞。孔洞的数量称为表面的亏格 genus。 通常情况下，我们只考虑亏格为零的多面体，即拓扑等价于球面的多面体。

总之，多面体的边界是由有限个有界的凸多边形面构成的集合，且满足以下条件:

1. 面之间"正确地"相交，如前文 (1) 所述
2. 每个点的邻域在拓扑上都是一个开的圆盘(open disk)，或者等价地说，每个顶点的环都是一条简单的多边形链
3. 表面是连通的，或者等价地说，其 1-骨架(1-skeleton)是连通的。

该边界是闭合的，并且包围了一个有界的空间区域。每条边恰好被两个面共享，这两个面称为相邻面 adjacent。

凸多面体也被称为多胞体(polytopes)，有时为了强调三维空间，也称为 3-多胞体。多胞体是一种凸多面体，连接其内部任意两点的线段都完全在该多面体内部。 正如凸多边形可以通过"每个顶点都是凸的"这一局部条件来刻画一样，多胞体也可以通过局部条件来定义，即要求所有二面角 dihedral angle 都是凸的\((≤ \pi)\)。 二面角是指一条边处，由包含其两个相邻面的平面所形成的空间内角。对于任何多胞体，每个顶点处所有面角(face angles)之和至多为 \(2 \pi\)， 但这一条件本身并不足以保证其凸性(见练习 4.1.6[5])。

培养几何直觉并检验想法，是深入熟悉几种典型的多面体的重要过程。因此，我们将花一些时间来讨论五种柏拉图多面体 Platonic solids。

4.1.2. 正多胞体(Regular Polytopes)

正多边形regular polygon是指边长相等且角度相等的多边形，比如等边三角形、正方形、正五边形、正六边形等等。 显然，正多边形有无穷多种，每个 \(n\) 都对应一个正多边形。现在我们可以研究正多面体 regular polyhedra，它们是凸的，因此通常被称为正多胞体 regular polytopes。 我们所能施加的最大正则性条件是，所有面都是全等的正多边形，并且每个顶点所连接的面的数量都是一样的。事实证明，这些条件蕴含了相等的二面角，因此二面角无需包含在定义中。

令人惊讶的是，只有五种不同的正多胞体！它们被称为柏拉图多面体 Polatonic solids，因为它们在柏拉图的《Timaeus》中有所论述。

现在我们来证明只存在五种正多面体。证明过程非常简单。直观的理解是，正多边形的内角随着顶点数的增加而增大，但每个顶点周围的空间是有限的。 设 \(p\) 为每个面的顶点数。那么每个面都是一个正 \(p\) 边形。 一个 \(p\) 边形的面角之和为 \(\pi(p - 2)\)(推论 1.2.5)，因此每个面角是其 \(1/p\)，即 \(\pi(1 - 2/p)\)。

设 \(v\) 为相交于一个顶点的面数。关键约束是，相交于一个顶点的面角和必须小于 \(2 \pi\)，这样才能保证多面体是凸的。 我们也可以从一个现象中直观感受到这点，如果多面体表面在顶点附近是平坦的，角之和恰好为 \(2 \pi\)，而尖锐顶点的角和则非常小。 因此，角和的值域为 \((0, 2\pi)\)。因此，如果我们有 \(v\) 个角，每个角均为 \(\pi(1-2/p)\)，那么它们的和必须小于 \(2\pi\)。 我们通过一系列代数运算变换这个不等式，得到一个特别方便的形式:

$$ \begin{equation}\label{f4.1} \begin{array}{rcl} v\pi (1 - 2/p) & < & 2 \pi \\ 1 - 2/p & < & 2 /v \\ pv & < & 2v + 2p \end{array} \end{equation} $$ $$ \begin{equation}\label{f4.2} \begin{array}{rcl} pv - 2v - 2p + 4 & < & 4 \\ (p-2)(v-2) & < & 4 \end{array} \end{equation} $$

其中，\(p\) 和 \(v\) 都是整数。因为多边形至少有三条边，所以 \(p ≥ 3\)。\(v > 3\) 这一点可能不太明显。 每个顶点至少要有三个面相交，因为只有两个面的顶点 \(v\) 无法形成"立体角 solid angle"。 这些限制足以将可能性限制在表 4.1 所列的范围内。例如，\(p = 4\) 且 \(v = 4\) 会导致 \((p - 2)(v - 2) = 4\)，这违反了不等式。 事实上，如果在四个正方形共用一个顶点，它们必须共面，这种情况不可能形成多面体。

表中所列的 \(p,v\) 取值的组合，为何能得出所声称的对象，这一点并不那么显然。这些数值提供的是局部信息，需要从中推断出全局结构。 在此我们不赘述这一推断过程。只需观察图 4.3 中的五个多面体，即可迅速发现它们符合 \(\{p, v\}\) 值。统计顶点数、边数和面数，即可得到表 4.2 中的数值。 名称中的希腊语前缀指的是面的数量: tetra = 4，octa = 8，dodeca = 12，icosa = 20。有时立方体(cube)也被称为"六面体 hexahedron"！

4.1.3. 欧拉公式(Euler's Formula)

1758年，欧拉(Leonard Euler)注意到亏格为零的多面体的顶点、边和面的数量之间存在一个显著的规律：顶点数和面数之和总是比边数多 2。而且这个规律适用于所有多面体。 例如，一个立方体有 8 个顶点和 6 个面，\(8 + 6 = 14\) 比它的 12 条边多 2。其余的正多面体也都满足同样的规律。如果我们分别用 \(V, E, F\) 表示一个多面体的顶点、边、面的数量， 那么著名的欧拉公式 Euler's formula 就是： $$ \begin{equation}\label{f4.3} V - E + F = 2 \end{equation} $$

或许有人会认为，发现这种规律并非什么了不起的成就，但欧拉必须先"发明"顶点和边的概念才能提出他的猜想。 数学家们花了多年时间才发展出严格的证明，尽管用现代方法证明起来并不难。现在我们来看证明。

4.1.4. 欧拉公式的证明(Proof of Euler's Formula)

我们的证明包含三个部分：

1. 将多面体表面转换为平面图。
2. 介绍关于树的定理。
3. 通过数学归纳法证明。

假设多面体由一种柔性材料制成，我们首先将多面体表面 \(P\) "展平"到一个平面上，可能会产生相当大的变形。 选择 \(P\) 的任意一个面 \(f\) 并将其移除，这会在表面上留下一个孔。现在，将这个孔不断拉伸，直到它远大于 \(P\) 的原始尺寸。 直观上应该可以理解，我们可以将该表面展平到平面上，从而得到一个平面图 \(G\)，即，多面体的 1-骨架(1-skeleton)。它是一个嵌入平面且边无交叉的图，其节点源自 \(P\) 的顶点， 其弧源自 \(P\) 的边。\(f\) 的边成为了 \(G\) 的外边界。除 \(f\) 之外的 \(P\) 的每个面都对应 \(G\) 的一个有界面，\(f\) 则是 \(G\) 的外部无界面。 展平后的立方体如图 4.4 所示。因此，如果我们把图 \(G\) 的这个外表面算作一个真正的面，那么多面体 \(P\) 的顶点、边和面就与图 \(G\) 的顶点、边和面一一对应。 我们可以基于该平面图证明欧拉公式。

第二步是证明当 \(G\) 是一棵树的结构时公式成立。当然，树是不可能由拉伸多面体得到的，但这对证明的最后一步很有帮助。 假设 \(G\) 是一棵有 \(V\) 个顶点和 \(E\) 条边的树。树的一个性质是 \(V = E + 1\)，在证明过程中，我们认定这个事实成立。 一棵树只包围或限定一个面，即图的外部无界面(exterior face)，因此 \(F = 1\)。现在欧拉公式就显而易见了：

$$ V - E + F = (E + 1) - E + 1 = 2 $$

证明的第三步也是最后一步，是对边的数量进行归纳。假设欧拉公式对所有连通且边数不超过 \(E - 1\) 的图都成立，并且设 \(G\) 是一个具有 \(V\) 个顶点、\(E\) 条边和 \(F\) 个面的图。 如果 \(G\) 是一棵树，那么之前的论证就足以完成证明，甚至无需使用归纳法。 假设 \(G\) 有一个环，并且设 \(e\) 是 \(G\) 中某个环的一条边。 图 \(G' = G \setminus e\) 是连通的，有 \(V\) 个顶点、\(E - 1\) 条边和\(F - 1\) 个面。那么移除 \(e\) 必然会将两个面合并成一个面。根据归纳假设，有

$$ V - (E-1) + (F-1) = 2 = V - E + F $$

证明结束。

4.1.5. 线性关系(Consequence: Linearity)

现在我们证明，欧拉公式表明多面体的顶点、边、面的数量之间存在线性关系：如果 \(V = n\)，则 \(E = O(n)\) 且 \(F = O(n)\)。这将允许我们在涉及多面体的复杂性分析中更灵活地使用"\(n\)"。

因为我们试图建立 \(E, F\) 关于 \(V = n\) 的函数的上界，所以我们可以放心地对多胞体的每个面进行三角剖分，因为这只会增加 \(E,F\) 而不会影响 \(V\)。 因此，在接下来的论证中，我们假设多胞体是单纯形(simplicial)，即，它的所有面都是三角形。如果我们逐个面地计算边数，那么由于每个面有三条边，我们得到 \(3F\)。 但由于每条边都被两个面共享，所以边的计数重复了。因此有 \(3F = 2E\)。代入欧拉公式即可得到线性上界：

$$ \begin{equation}\label{f4.4} \begin{array}{rcl} V - E + F & = & 2 \\ V - E + 2E/3 & = & 2 \\ V - 2 & = & E / 3 \\ E & = & 3V - 6 < 3V = 3n = O(n) \\ F = 2E / 3 & = & 2V - 4 < 2V = 2n = O(n) \end{array} \end{equation} $$

我们将其总结为一个定理，以备后用：

Cromwell(1997) 是获取多面体更多信息的优质参考资料。

4.1.6. 练习

1. 封闭且有界Closed and bounded。论证文中对多面体的定义保证了它是封闭且有界的。
2. 不完善的定义1Flawed definition 1。以下是一个"不完善的"多面体定义。将以此定义的物体称为\(\text{polyhedra}_1\)。找出符合\(\text{polyhedra}_1\)定义但并非本文中定义的多面体物体。
       \(\text{polyhedra}_1\) 是由有限个多边形围成的空间区域，其中每个多边形至少与其他多边形共用一条边，且每条边恰好被两个多边形共用。
3. 不完善的定义2Flawed definition 2。与上一个练习相同，但使用以下定义：
       \(\text{polyhedra}_2\) 是由有限个多边形围成的空间区域，其中每个多边形的每条边都恰好与其他一个多边形共享，并且这些多边形的任何子集都不具有相同的性质。
4. [easy] 八面立方体Cuboctahedron。在八面立方体上验证欧拉公式。八面立方体是通过切掉单位立方体的每个角被而形成的多面体， 切掉的每个角都变成边长为 \(\sqrt{2}/2\) 的等边三角形，立方体的每个面都变成菱形，边长为 \(\sqrt{2}/2\) 的正方形。请先画出该多面体的草图。
5. 牛奶盒(Saul Simhon)Milk carton。找到一个非凸多面体的例子，使得围绕每个顶点的面角之和不超过 \(2 \pi\)。
6. 适用于非零亏格的多面体欧拉公式Euler's formula for nonzero genus。欧拉公式存在一个适用于任意亏格多面体的版本。根据亏格为 1 的多面体的经验证据(拓扑等价于环面)推测该公式。
7. [easy] 不存在七边形No 7-edge polyhedron。证明不存在恰好有七条边的多面体。
8. FV-空间中的多面体Polyhedra in FV-space。证明每个满足以下条件的整数对 (F, V) 都存在一个由 \(F\) 个面和 \(V\) 个顶点组成的简单多面体。 $$ \frac{1}{2}F + 2 ≤ V ≤ 2F -4 $$
9. [difficult] 多面体环面Polyhedral torus。构建一个多面体环面至少需要多少个三角形？(显然四个三角形不够。)至少需要多少个顶点？ 设计一个多面体环面，并尝试使其曲面的组合规模（以这两种方式衡量）最小化。
10. Gauss-Bonnet定理Gauss-Bonnet theorem。计算几个亏格为 0 的多面体所有顶点的面角之和，并提出一个猜想。