6.6 高阶维诺图
(Higher-Order Voronoi Diagrams)

本节将探讨排列与维诺图之间的联系，这种联系在5.8节中已有预告。 我们将仅详细阐述一维维诺图之间的关系，更有意思的二维情况则主要通过类比的方式来解释。这种联系的重点在于被称为"高阶沃罗诺伊图(higher-order Voronoi diagrams)"的对象， 我们将在建立必要的理论基础之后对其进行解释。

6.6.1. 一维图 (One-Dimensional Diagrams)

回顾5.8.1节，\(x\) 轴上的一组点 \(P = \{x_1, \dots, x_n\}\) 被映射为一组与抛物线 \(y = x^2\) 相切的直线。 切点位于 \(x_i\) 的正上方 \((x_i, x_i^2)\)。切线方程为 \(T_i : y = 2x_i x - x_i^2\)。注意，这条切线正是 \(\mathbb{D}((x_i, x_i^2))\)。 我们不妨假设这组点是有序的，即，\(x_i < x_{i+1}\)。我们证明了两个相邻切线交点的 \(x\) 坐标是其生成点之间的中点。\(x_i\) 和 \(x_{i+1}\) 对应的切线相交于 \(\frac{1}{2}(x_i + x_{i+1})\)。因此，这些交点垂直投影到 \(P\) 的一维维诺图，即 \(P\) 的中点集。

现在我们考虑由这 \(n\) 条抛物线切线形成的线排列，如图 6.9 所示，其中 \(P = \{-15, -3, 1, 10, 20\}\)。注意，抛物线完全包含在该排列的一个面 \(C\) 内， 正是这个面的边界的投影给出了 \(P\) 的维诺图 \(x = \{-9, -1, 5\frac{1}{2}, 15\}\)。换一种方式来看会很有意思，想象着放下一条垂直线 \(x = b\)。 它遇到的 \(C\) 的第一条边，就将 \(b\) 映射到其所在的维诺单元中(\(x\) 轴上的一个线段)。Imagine dropping down the vertical line \(x = b\). The first edge of \(C\) encountered maps to the Voronoi cell (a segment on the \(x\) axis) in which \(b\) lies.

在引入新的联系之前，我们给出这一观察结果的另一种解释，这在5.7.1节中已经提到过。 设 \(T\) 为抛物线在 \(x = a\) 上方的切线，即 \(T\) 为 \(y = 2ax - a^2\)。我们断言，\(x = b\) 上方抛物线与 \(T\) 之间的垂直距离 \(d\) 是 \(a\) 和 \(b\) 之间距离的平方。 如图 6.10 所示。可以通过简单的计算来验证，\(d = b^2 - (2ab - a^2) = (b - a)^2\)。这一现象与前文之间的关系现在应该很清楚了。 如果在放下 \(x = b\) 时，先遇到 \(T_i\) 后遇到 \(T_j\)，那么 \(T_i\) 在 \(b\) 上方离抛物线比 \(T_j\) 更近，因此 \(b\) 离 \(x_i\) 比离 \(x_j\) 更近。

上述讨论，我们可以得出以下结论。切线的垂直排序对应于最近邻排序。

最后我们触及到了核心。定义2阶维诺图(2nd-order Voronoi diagram)，将相关空间(刚才的讨论为 \(x\) 轴)前两个最近邻点划分为若干区域，相同区域中的点具有相同的两个最近邻站点。 至于谁第一谁第二是无关紧要的。因此，如果 \(a\) 的最近邻是 \(x_i\) 次近邻是 \(x_j\)，那么它与一个最近邻是 \(x_j\) 次近邻是 \(x_i\) 的点 \(b\) 处于同一个2阶维诺区域中。 2阶图隐含在由点构成的抛物线排列(parabola arrangement)的边中，这些点的垂直上方恰好有一条直线。由于每条边都位于一条直线上，所以他们上方(above)或之上(on)有两条直线。 这些边构成了所谓的排列的2-层结构(2-level)。图 6.9 中排列的 2-层结构在图 6.11 中用虚线高亮显示。 2-层顶点的投影将 \(x\) 轴划分为若干单元格，这些单元格中的点具有相同顺序的前两个最近邻。 因此在图 6.11 中，所有 \(x > 15\) 的点都有 \((20, 10)\) 作为其两个最近邻。所有 \(10\frac{1}{2} < x < 15\) 的点都有 \((10, 20)\) 作为最近邻。 所有 \(5\frac{1}{2} < x < 10\frac{1}{2}\) 的点都有 \((10, 1)\) 作为最近邻。等等。由 2-层投影所产出的这种直线划分比2阶维诺图更精细， 因为在那个图中邻居的顺序并不重要。所以在图 6.11 中，所有点 \(x > 10\frac{1}{2}\) 都有 \(\{10, 20\}\) 作为其两个最近邻的集合。 我们现在论证2阶维诺图的过渡点是2-层与3-层排列之间交点的投影。

将排列的 \(k\)-层(\(k\)-level)定义为边的集合，这些边上的点正上方恰好有 \(k-1\) 条直线，包含这些边的端点。排列的边是开线段。 我们不要求顶点上方有特定数量的直线，因为它们上方可能没有 \(k-1\) 条线。图 6.11 用点高亮了3-层结构。设 \(a\) 为2-层与3-层交点处顶点的投影。图中圈出了这三个顶点。 设垂直线 \(x = a + \epsilon\) 从上到下遇到的前三条切线为 \((A, B, C)\)，其中 \(\epsilon > 0\) 是一个很小的数。在此 \(x\) 处，\(B\) 位于 2-层，\(C\) 位于 3-层。 那么在 \(a\) 的另一侧，直线 \(x = a - \epsilon\) 遇到这些切线的顺序为 \((A, C, B)\)，因为此处 \(C\) 在 2-层上，而 \(B\) 在 3-层上，且 \(B\) 和 \(C\) 在 \(x = a\) 处相交。 因此，\(x = a\) 代表了前两个最近邻从 \(\{A, B\}\) 到 \(\{A, C\}\) 的变化。这表明 2-层和 3-层共有的顶点确实代表了二阶维诺区域的过渡。 同样，2-层的其他顶点(那些不在 3-层上的顶点\)代表了两个最近邻顺序的交换，而不改变这些邻居的集合。

我们刚才讨论的内容对任意 \(k\) 都成立:

注意，该定理甚至对 \(k = 1\) 也"适用"。1-层与 2-层之间的交点正是 1-层的顶点，这些顶点也是包含抛物线的单元格的顶点，它们投影为普通的维诺图，这可以被看作是 1 阶维诺图。

6.6.2. 二维图

我们不会在二维空间中推导任何结果，但正如读者所预期的那样，一维中的所有定义和结果都完全可以直接推广。给定平面上的一组点， 如5.8.2 节所述，在这些点上方用抛物面的切平面，构造一个排列。 维诺图是 1-层(1-level)的投影，包含抛物面的单元格的边和顶点。\(k\)-层是一个由面(以及其闭包中的边和顶点)组成的起伏"薄片(sheet)"。 \(k\)阶维诺图是 \(k\)-层和 \((k+1)\)-层交集的投影，这是一组边和顶点的集合。图 6.12 显示了一个简单的 2 阶维诺图。因此，所有高阶维诺图在精确意义上都蕴含在切平面的排列中。

这也表明，所有这些图的总复杂度为 \(O(n^3)\)，因为这些层都蕴含在一个复杂度为 \(O(n^3)\) 的排列中(根据定理 6.4.1)， 并且层之间没有共享面。通过构造平面排列，在 \(O(n^3)\) 的时间内构造所有 \(k\) 阶维诺图，\(k = 1, \dots, n - 1\) 并不难。

6.6.3. 练习

1. 最远点维诺图 Furthest-point Voronoi diagram。证明最远点维诺图(图 5.19)与 \((n-1)\) 阶维诺图是相同的。
2. 一维空间中的 \(k\) 阶维诺图 \(k\)th-order Voronoi diagram in dimension 1。在一维空间中，一个 \(k\) 阶维诺图里有多少个区域?
3. 单元是凸的 Cells are convex。证明 \(k\) 阶维诺图的单元是凸集。
4. 界定多个单元的平分线 Bisector bounding more than one cell。举例证明两个点的平分线可能会界定出 \(k\) 阶维诺图中两个不相邻的单元。
5. \(k\)-层 \(k\)-levels。证明简单直线排列中的 \(k\)-层是一条将平面分割成两部分的折线链(polygonal chain)。