Voronoi 图

形式陈述 ​

设 $(X,d)$ 是度量空间公理库度量空间Metric space配备非负、对称、正定并满足三角不等式的距离函数的集合。，$S\subset X$ 是有限且非空的不同站点集合。站点 $p\in S$ 的闭 Voronoi cell 定义为

$$\mathrm{Vor}(p)=\{x\in X:d(x,p)\le d(x,q)\text{对所有 }q\in S\}.$$

这些闭单元覆盖 $X$，但在等距位置可以重叠；把各单元内部、公共边界和交点组成的 subdivision 称为 Voronoi 图。在 Euclidean 平面中，条件 $\Vert x-p\Vert \le \Vert x-q\Vert$ 定义 $p,q$ 垂直平分线一侧的闭半平面，因此每个 cell 是有限个半平面的交，必为凸区域，但可能无界。一般位置下，Voronoi edge 上的点对两个站点等距且不比其他站点远，Voronoi vertex 通常由三个站点共同确定。

直觉 ​

Voronoi 图回答“每个位置应归给最近的哪个站点”。两个站点竞争的分界是它们的等距集合；再与其余站点的优势区域相交，才留下真实 cell 边。它把连续平面压缩成有限的邻接结构：cell 记录最近站点，edge 记录一次并列，vertex 记录多方并列。

计算几何公理库计算几何问题Computational geometry problem以点、线段、多边形等几何对象为输入并要求组合或数值几何输出的问题族。关心的不只是画出这些边，还要保存其组合关系和无界射线。闭 cell 的共享边界是定义的一部分，不应误认为分区失败；实际查询若必须返回唯一站点，可另行规定平局规则。

例子与边界 ​

只有两个 Euclidean 站点 $p=(-1,0)$ 与 $q=(1,0)$ 时，直线 $x=0$ 是二者的等距边界，左右两个闭半平面分别是 $p,q$ 的 cell。加入第三个不共线站点后，三条相关垂直平分线交于三角形外接圆圆心；若该点不受其他站点压制，它成为一个 Voronoi vertex。

位于站点凸包边界上的站点拥有朝外延伸的无界 cell，内部站点的 cell 则有界。因此“cell 都是多边形”不能被误读为“都是有界多边形”。四个站点共圆时，圆心可同时属于四个 cell，Voronoi vertex 的度数超过一般位置下的三；算法若假设每个顶点恰接三条边，必须先排除这种退化。

换用 $L_1$ 距离后，两个站点的等距集合可能包含折线段甚至二维退化片，Euclidean 半平面推导和凸性细节不能原样搬用。若站点有权重，最近关系还会变成加权 Voronoi 图；加性权重与乘性权重产生不同边界，不能只在距离公式旁补一个系数便视为同一结构。

推论与应用 ​

Voronoi 图用于最近邻定位、设施服务区、网格生成和运动规划。Euclidean 平面中，站点 cell 相邻关系与 Delaunay 结构对偶：共享一条 Voronoi edge 的站点形成候选邻接，这让连续最近距离问题转化为离散平面图。

无界 cell 与凸包、Voronoi vertex 与空圆条件提供了可核验的几何证书。构造算法可以采用分治或 Fortune 扫描线，但这些算法需要自己的事件不变量和退化处理；定义页只固定目标 subdivision 及其距离语义。

参考资料

• Franz Aurenhammer, “Voronoi Diagrams—A Survey of a Fundamental Geometric Data Structure,” ACM Computing Surveys 23(3), 1991, pp. 345–405.
• Mark de Berg et al., Computational Geometry: Algorithms and Applications, 3rd ed., Springer, 2008, Ch. 7.