4.6 更高维度
(Higher Dimensions)

尽管本书不会涉及三维以上的计算几何内容，但如果对这一富有成果且至关重要的领域只字不提，那未免有些失礼。本节（连同书中其他地方的简要提及）将是我们向该方向致意。领会高维几何是一项智力挑战，读者在这里只能浅尝辄止。若想深入了解，Banchoff (1990) 和 Rucker (1984) 的著作是很好的资源。探索高维度的最佳途径是类比低维度。在跃入超空间之前，最好先考察零维、一维、二维和三维的例子，以此为你的直觉助跑蓄势。

4.6.1. 坐标系(Coordinates)

数轴上的一个点可以用一个单独的数字来表示，即它的数值或位置。这可以被看作是一个一维点，因为它所在的空间，直线，是一维的。二维空间中的点可以由两个坐标 $(x, y)$ 确定，三维空间中的点则由三个坐标 $(x, y, z)$ 确定。这里跨越进高维空间轻而易举，四维空间中的一个点需要四个坐标来确定，比如 $(x, y, z, t)$。如果我们把 $(x, y, z)$ 看作空间坐标，把 $t$ 看作时间，那么这四个数字就共同确定了一个时空中的"事件(event)"。除了用于表示时空的四维空间外，还有许多其他可能的高维空间。比如，我们可以用身高、袖长、裤长、颈围、腰围，来表示一个人的关键穿衣特征。这样一来，每个人都可以被看作五维空间中的一个点: (身高, 臂长, 腿长, 颈围, 腰围)。

遗憾的是，仅仅思考坐标并不能让我们对高维几何产生多少深刻的洞见。为此，我们将转向超立方体(hypercube)。

4.6.2. 超立方体(Hypercube)

零维立方体是一个点。一维立方体是一条线段。二维立方体是一个正方形。三维立方体就是我们常见的普通立方体。在跃入四维空间之前，让我们先整理一些数据。

我们可以将 $d$ 维立方体看作是由两个 $d-1$ 维立方体构建而成的，具体如下：取一个一维立方体(一个点)，并在第二维上对其进行拉伸，生成一个二维立方体(一条线段)。然后将一条线段沿与其正交的方向滑动，扫出一个正方形。将一个正方形沿垂直于其平面的方向提升，扫出一个立方体。参见图4.20。

现在到了跨越的一步。从一个拥有 8 个顶点和 12 条边的立方体开始。拖拽着原立方体的顶点在第四个维度上移动到终点的立方体，扫过的空间就得到了一个新的对象。它就是一个超立方体hypercube，即四维立方体。它拥有 16 个顶点(起始和终止立方体各贡献 8 个)和 32 条边(各贡献 12 条，加上 8 条新生成的边)。参见图 4.21。注意，边的数量 $E_d$ 等于低一维度的边数的两倍 ($2E_{d-1}$) 加上顶点的数量 $V_{d-1}$。

一般超立方体的顶点坐标可以通过前 $2^d$ 个整数的二进制数字方便地生成，该超立方体是这 16 个点的凸包。

Dim $d$	Name	$V_d$	$E_d$
0	point	1	0
1	segment	2	1
2	square	4	4
3	cube	8	12
4	hypercube	16	32
$d$	d-cube	$2^d$	$2 E_{d-1} + V_{d-1}$

$$ \begin{aligned} 0 &\to (0, 0, 0, 0) & 8 &\to (1, 0, 0, 0) \\ 1 &\to (0, 0, 0, 1) & 9 &\to (1, 0, 0, 1) \\ 2 &\to (0, 0, 1, 0) & 10 &\to (1, 0, 1, 0) \\ 3 &\to (0, 0, 1, 1) & 11 &\to (1, 0, 1, 1) \\ 4 &\to (0, 1, 0, 0) & 12 &\to (1, 1, 0, 0) \\ 5 &\to (0, 1, 0, 1) & 13 &\to (1, 1, 0, 1) \\ 6 &\to (0, 1, 1, 0) & 14 &\to (1, 1, 1, 0) \\ 7 &\to (0, 1, 1, 1) & 15 &\to (1, 1, 1, 1). \end{aligned} $$

4.6.3. 正多胞体 (Regular Polytopes)

我们看到在三维空间中有且仅有五个不同的正多胞体。在四维空间中有且仅有六个正多胞体。其中一个是超立方体。但也有惊喜，其中一个正多胞体被称为 600-cell，它由 600 个四面体"面(facets)"组成！直到十九世纪，四维正多胞体的列表才完成，这距离三维多胞体的构建大约过了 2000 年。在维度 $d \ge 5$ 的空间中，只有三个正多胞形，即四面体、立方体和八面体的推广形式。参见 Coxeter (1973)。

4.6.4. 高维凸包

目前已经有大量研究，探索构建高维点集凸包的算法。在极其广泛的应用场景中都会遇到这样的问题，这里我们举三个例子。首先，有一种特定类型的程序，其条件语句处走向一个分支而非另一个分支的概率，可以被建模为多维多胞体(polytopes)体积之比，其维度取决于代码的复杂度(Cohen & Hickey 1979)。其次，凸光源的"反半影antipenumbra"的计算，可以通过计算五维空间中的点集凸包来解决(Teller 1992)。所谓的反半影(antipenumbra)，是指能看到光源的一部分但非全部的空间体积。第三，三维点的三角分割可以通过构建四维凸包得到，我们将在 5.7.2 节中介绍这个优美的联系。此类三角分割在众多应用中都是必需的。例如，三维物体的动态应力分析中，通过将物体离散化为小单元(通常是四面体)来求解微分方程。这需要对物体表面的一组点进行三角分割。由于这种三维与四维之间的联系以及其他原因，四维凸包的需求量很大，并且已经开发出了许多高质量的软件包(Amenta 1997)。

不幸的是，获得高效算法存在一个根本性的障碍，凸包的结构非常复杂，以至于仅仅将其打印出来这一操作就给算法设定了一个很高的下界。 Klee(1980) 证明了 $d$ 维空间中 $n$ 个点的凸包可能拥有 $\Omega(n^{\lfloor d/2 \rfloor})$ 个面(facets)。特别地，$d=4$ 维空间中这种复杂度关系可能是二次方的，因此不可能存在 $O(n \log n)$ 的算法。尽管如此，人们已经开发出了在现有情况下尽可能高效的算法，最坏情况下的复杂度为 $O(n \log n + n^{\lfloor d/2 \rfloor})$。此外，还有对输出大小敏感的算法可用，其中一种算法生成 $F$ 个面所需的时间为 $O(ndF)$(Avis & Fukuda 1992)。

4.6.5. 练习(Exercises)