5.8 与排列的联系
(Connection to Arrangements)

我们已经展示了如何从抛物面变换推导出 Delaunay 三角分割，之后就可以很容易获得维诺图。实际上，也有可能直接从抛物面变换获得维诺图。 尽管对这一点的充分理解需要等到下一章(6.6节)， 但趁着上一节刚推出相关公式，本节我们趁热打铁，先来浏览一下这种联系。

5.8.1 一维维诺图 (One-Dimensional Voronoi Diagrams)

考虑在 5.7.1 节(式 5.4)中研究的抛物线的两条切线，一条位于 \(x = a\) 上方，另一条位于 \(x = b\) 上方:

$$ \begin{aligned} z &= 2ax - a^2, \\ z &= 2bx - b^2. \end{aligned} \tag{5.12} $$

它们在哪里相交? 联立求解这些方程可得:

$$ \begin{aligned} 2ax - a^2 &= 2bx - b^2 \\ x(2a - 2b) &= a^2 - b^2 \\ x &= \frac{(a + b)(a - b)}{2(a - b)} \\ x &= \frac{a + b}{2} \end{aligned} \tag{5.13} $$

因此，相邻切线的交点投影即为一维点集的维诺图。

5.8.2. 二维维诺图

考虑在 5.7.2 节(式 5.8)中分析的抛物面的两个切平面，一个位于 \((a, b)\) 上方，另一个位于 \((c, d)\) 上方:

$$ z = 2ax + 2by - (a^2 + b^2), \tag{5.14} $$ $$ z = 2cx + 2dy - (c^2 + d^2). \tag{5.15} $$

它们在哪里相交？联立求解这些方程可得

$$ \begin{aligned} 2ax + 2by - (a^2 + b^2) & = 2cx + 2dy - (c^2 + d^2) \\ x(2a - 2c) + y(2b - 2d) & = (a^2 - c^2) + (b^2 - d^2) \end{aligned} \tag{5.16} $$

这个方程正是从 \((a, b)\) 到 \((c, d)\) 的线段的垂直平分线。如图 5.31 所示。

如果我们从 \(z = +\infty\) 处观察这些(不透明的)的切平面，假设抛物面是透明的，那么它们只在第一个交点之前可见。 它们的第一个交点即为生成切平面的站点之间的平分线。这些第一交点的投影正是维诺图。

如此，我们得到了一个意义非凡的结论: 从 \(z = -\infty\) 观察投影到抛物面上的点，看到的是 Delaunay 三角剖分。 而从 \(z = +\infty\) 观察在这些点处与抛物面相切的平面，看到的则是维诺图。