5.2 定义与基本性质
(Definitions and Basic Properties)
设 \(P = \{p_1, p_2, \ldots, p_n\}\) 为二维欧式平面上的一组点。这些点被称为站点 sites。我们将平面上的每一点分配给离它最近的站点来对平面进行划分。 所有被分配给 \(p_i\) 的点构成了维诺区域(Voronoi region) \(V(p_i)\)。\(V(p_i)\) 包含所有距离 \(p_i\) 都不比到任何其他站点远的点：
$$ \begin{equation}\label{f5.1} V(p_i) = \{x : |p_i - x| \le |p_j - x| \; \forall j \neq i\} \end{equation} $$注意，我们将该集合定义为闭集。有些点没有唯一的最近站点。所有具有不止一个最近邻的点构成了该站点集的维诺图(Voronoi Diagram) \(\mathcal{V}(P)\)。 稍后我们在为比点更一般的对象集合上定义维诺图。在详细说明较大 \(n\) 时的性质之前，我们首先观察仅包含几个站点的图。
两个站点。仅考虑两个站点 \(p_1, p_2\)。令 \(B(p_1, p_2) = B_{12}\) 为线段 \(p_1 p_2\) 的垂直平分线。 那么 \(B_{12}\) 上的每一点 \(x\) 到 \(p_1\) 和 \(p_2\) 的距离相等。这可以通过图 5.2 中的三角形 \((p_1, p_2, x)\) 来看出。 根据欧几里得的"边角边 side-angle-side"定理，有 \(|p_1x| = |p_2x|\)。
三个站点。对于三个站点，很明显在三角形 \((p_1, p_2, p_3)\) 之外，维诺图一定包含垂直平分线 \(B_{12}, B_{23}, B_{31}\)。 不太清楚的是三角形附近的情况。再次根据欧几里得几何，三角形三条边的垂直平分线都经过同一点，即外心(circumcenter)， 也就是经过三角形三个顶点的唯一圆(外接圆)的圆心。因此，三个点的维诺图必然如图 5.3 所示。但是，三角形的外心并不总是像图中所示那样位于三角形内部。
5.2.1. 半平面(Halfplanes)
现在我们还不知道如何推广到超过三个点的情况，但可以肯定的是垂直平分线 \(B_{ij}\) 将发挥作用。设 \(H(p_i, p_j)\) 是以 \(B_{ij}\) 为边界且包含 \(p_i\) 的闭半平面。 那么 \(H(p_i, p_j)\) 可以看作是所有距离 \(p_i\) 比距离 \(p_j\) 更近的点的集合。现在回想一下，\(V(p_i)\) 是所有距离 \(p_i\) 比距离任何其他站点更近的点的集合。 换句话说，这些点距离 \(p_i\) 比距离 \(p_1\) 更近，并且距离 \(p_i\) 比距离 \(p_2\) 更近，并且距离 \(p_i\) 比距离 \(p_3\) 更近，依此类推。 这表明我们可以为 \(V(p_i)\) 写出如下方程：
$$ \begin{equation}\label{f5.2} V(p_i) = \bigcap_{i \neq j} H(p_i, p_j) \end{equation} $$其中符号意味着交集是在所有满足 \(i \neq j\) 的 \(i\) 和 \(j\) 上取的。注意，连词并且已被转化为集合交集。 方程(\(\ref{f5.2}\)) 直接给出了维诺图的一个重要性质: 维诺区域是凸的，因为任意数量半平面的交集是一个凸集。当这些区域有界时，它们是凸多边形。 维诺区域的边被称为维诺边(Voronoi edges)，顶点被称为维诺顶点(Voronoi vertices)。注意，位于维诺边内部的点有两个最近站点，而维诺顶点至少有三个最近站点。
四个站点。如图 5.4(a) 所示，有四个点构成了矩形四个角，其维诺顶点的度为四。现在假设其中一个站点被轻微移动，如图 5.4(b) 所示。 在某种意义上，这个图是正常的，而图 5.4(a) 中的图是异常的，或者是"退化的"(degenerate)。它的退化之处在于存在四个共圆点。后面我们会发现排除这种类型的退化是有用的。
多个站点。图 5.5 展示了一个包含许多站点的典型示例。图中未显示出一个维诺顶点，图中向左延伸的两条两条近乎水平的射线，实际并不完全平行， 它们相交于图左侧约 70 厘米处的一个维诺顶点上。
5.2.2. 图的大小 (Size of Diagram)
\(n\) 个站点就恰好有 \(n\) 个维诺区域，但维诺图可能得组合数量理论上可能是 \(n\) 的二次方，因为任何特定的维诺区域可能拥有 \(\Omega(n)\) 条维诺边(练习 5.3.3[4])。 但是，我们现在证明事实并非如此，即图的总大小为 \(O(n)\)。
假设空间中四个点不是共圆的，那么每个维诺顶点的度数均为三。按如下方式构建维诺图 \(\mathcal{V}(P)\) 的对偶图 \(G\)(第 4.4 节)， \(G\) 的节点是 \(\mathcal{V}(P)\) 中的站点(sites)，如果两个节点对应的维诺多边形共享一条维诺边，一条长度为正的边，那么这两个节点由一条弧连接。
注意这是一个平面图，我们可以将每个节点都关联到站点上，并且所有关联到该节点的弧可以像多边形边一样按照角度排序。此外，\(G\) 的所有面都是三角形， 对应于度数为三的维诺顶点。我们会在后文中更清楚的描述这一约束。参见图 5.6。
根据欧拉公式可以推出，具有 \(n\) 个顶点的三角分割平面图有 \(3n - 6\) 条边和 \(2n - 4\) 个面，参见第 4.1.5 节定理 4.1.1。 因为 \(G\) 的每条弧都穿过一条维诺边，所以\(G\) 的边与维诺边相对应。又因为 \(G\) 的面与维诺顶点相对应，所以维诺顶点、边和面的数量均为 \(O(n)\)。
如果我们现在去掉四个点不共圆的假设，该图仍然是平面图，但不一定是三角分割的。例如，图 5.4(a) 所示的对偶图是一个四边形。 但是这种非三角分割图具有更少的边和面，因此 \(O(n)\) 的界限仍然成立。根据边数的上界 \(3n - 6\)，可以推出，维诺多边形的平均边数不可能超过六(练习 5.3.3[5])。