5.3 Delaunay 三角分割
(Delaunay Triangulations)
1934年，Delaunay 证明了，当使用直线绘制对偶图时，就会生成维诺站点 \(P\) 的一个平面三角分割，前提是不存在四个站点共园。 这一结构现在被称为 Delaunay triangulation \(\mathcal{D}(P)\)。图 5.6 展示了图 5.5 中沃罗诺伊图对应的德劳内三角分割， 图 5.7 则展示了叠加在相应维诺图之上的德劳内三角分割。需要注意的是，在对偶图中使用直线连接并不一定能避免线段交叉。 正如在图 5.7 中所示，两个站点之间的对偶线段并不一定穿过它们维诺区域之间共享的维诺边。我们目前暂不证明 Delaunay 定理。 等到我们掌握了更多关于维诺图和 Delaunay 三角分割的性质之后，证明将变得非常简单。
 |
 |
5.3.1. Delaunay三角分割的性质 (Properties of Delaunay Triangulations)
由于 Delaunay 三角分割和维诺图是对偶结构，它们在某种意义上包含相同的信息，只是表示形式不同。为了掌握这些复杂的结构，必须彻底理解 Delaunay 三角剖分与其对应的维诺图之间的关系。 这里我们不加证明地列出了几个 Delaunay 性质，其中只有性质 D6 和 D7 之前没有提到过。固定一个站点集合 \(P\)。
- \(\mathcal{D}(P)\) 是 \(\mathcal{V}(P)\) 的直线对偶(straight-line dual)。这是由定义决定的。
- 如果 \(P\) 中没有四个点共圆，那么 \(\mathcal{D}(P)\) 是一个三角分割，每个面都是三角形。这是 Delaunay 定理。\(\mathcal{D}(P)\) 的面被称为 Delaunay 三角形。
- \(\mathcal{D}(P)\) 的每个三角形面对应 \(\mathcal{V}(P)\) 的一个顶点。
- \(\mathcal{D}(P)\) 的每条边对应 \(\mathcal{V}(P)\) 的一条边。
- \(\mathcal{D}(P)\) 的每个节点对应 \(\mathcal{V}(P)\) 的一个区域。
- \(\mathcal{D}(P)\) 的边界是站点的凸包。
- \(\mathcal{D}(P)\) 的每个三角形面的内部不包含任何站点。
这里的性质 D6 和 D7 是最有趣的；它们可以在图 5.6 和 5.7 中得到验证。
5.3.2. 维诺图的性质 (Properties of Voronoi Diagrams)
- 每个维诺区域 \(V(p_i)\) 都是凸的。
- 当且仅当 \(p_i\) 位于点集的凸包上。\(V(p_i)\) 是无界的
- 如果 \(v\) 是 \(V(p_1), V(p_2), V(p_3)\) 交界处的一个维诺顶点，那么 \(v\) 是由 \(p_1, p_2, p_3\) 确定的圆 \(C(v)\) 的圆心。这一论断可推广至任意度数的维诺顶点。
- \(C(v)\) 是对应于 \(v\) 的 Delaunay 三角形的外接圆。
- \(C(v)\) 的内部不包含任何站点。
- 如果 \(p_j\) 是 \(p_i\) 的最近邻，那么 \((p_i, p_j)\) 是 \(\mathcal{D}(P)\) 的一条边。
- 如果存在某个经过 \(p_i\) 和 \(p_j\) 的圆不包含其他站点，那么 \((p_i, p_j)\) 是 \(\mathcal{D}(P)\) 的一条边。反之亦成立，对于每条 Delaunay 边，都存在某个空圆。
性质 V7 是最不直观的，它是 Delaunay 边的重要特性，将在后面的几个证明中用到。我们将只给出这个性质的证明。
定理 5.3.1. 当且仅当存在一个经过 \(a\) 和 \(b\) 的空圆，有，\(ab \in \mathcal{D}(P)\)。该圆所界定的闭圆盘内除了 \(a\) 和 \(b\) 之外不包含 \(P\) 的任何其他站点。
证明: 如果 \(ab\) 是一条 Delaunay 边，那么 \(V(a)\) 和 \(V(b)\) 共享一条长度为正的边 \(e \in \mathcal{V}(P)\)。 在 \(e\) 的内部取一点 \(x\) 作为圆心画圆 \(C(x)\)，半径等于到 \(a\) 或 \(b\) 的距离。这个圆显然不包含其他站点。 假设站点 \(c\) 在圆上或圆内，那么 \(x\) 也会在 \(V(c)\) 中，但是 \(x\) 只在 \(V(a)\) 和 \(V(b)\) 中。
假设存在一个经过 \(a\) 和 \(b\) 的空圆 \(C(x)\)，圆心为 \(x\)。我们的目标是证明 \(ab \in \mathcal{D}(P)\)。因为 \(x\) 到 \(a\) 和 \(b\) 的距离相等， 所以 \(x\) 位于 \(a\) 和 \(b\) 的维诺区域的交集内。因此，\(x \in V(a) \cap V(b)\)。因为除了 \(a\) 和 \(b\)之外，\(C(x)\) 的边界上没有其他点， 我们可以自由地微调 \(x\) 并保持它是经过 \(a\) 和 \(b\) 的空圆。特别地，我们可以沿着 \(a\) 和 \(b\) 之间的垂直平分线\(B_{ab}\) 移动 \(x\)， 在保持空圆的同时，保持到 \(a\) 和 \(b\) 的等距性。参见图 5.8。因此 \(x\) 位于 \(V(a)\) 和 \(V(b)\) 共享的一条正长度的边 \(B_{ab}\) 的子集上，且 \(ab\) 因此属于 \(\mathcal{D}(P)\)。
我们将其他性质的证明留给直觉、练习，或 5.7.2 节。
5.3.3. 练习
- [easy] 正多边形 Regular polygon。描述正多边形顶点的维诺图和 Delaunay 三角分割。
- 无界区域 Unbounded regions。证明性质 V2，当且仅当 \(p_i\) 位于点集的凸包上，\(V(p_i)\) 是无界的。 不要假设对应的 Delaunay 性质 D6 成立，但证明中可以使用任何其他 Delaunay 或维诺图性质。
- 最近邻 Nearest Neighbors。证明性质 V6，如果 \(p_j\) 是 \(p_i\) 的最近邻，那么 \((p_i, p_j)\) 是 \(\mathcal{D}(P)\) 的一条边。 证明中可以使用任何 Delaunay 或维诺图性质。
- 高度数 Delaunay 顶点 High-degree Delaunay vertex。设计一组 \(n\) 个点，其中 \(n\) 为任意值，且没有四点共圆，使得 Delaunay 三角分割中的某一个顶点的度为 \(n - 1\)。
- 维诺多边形边数的平均值 Average number of Voronoi polygon edges。证明对于任意 \(n\) 个点的集合，对所有维诺区域取平均，其维诺多边形的边数不超过 6。 (Preparata & Shamos 1985, p. 211)。
- Pitteway 三角分割 Pitteway triangulations。如果对于每个三角形 \(T = (a, b, c)\)，\(T\) 中的每一点在 \(P\) 的点集中都有 \(a,b,c\) 之一作为其最近邻。
那么我们说该三角分割为点集 \(P\) 的 Pitteway 三角分割 (Okabe et al. 1992, p. 90)。
- 举例说明并非每个 Delaunay 三角分割都是 Pitteway 三角分割。
- 举例，一些 Delaunay 三角分割同时也是 Pitteway 三角分割。