Voronoi 图

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 的度数超过一般位置下的三；算法若假设每个顶点恰接三条边，必须先排除这种退化。

一般度量下，连“各 cell 的内部不重叠”也不保证。例如三点离散度量空间 $X=\{p,q,r\}$，取站点集 $S=\{p,q\}$；$r$ 同时属于两个 cell，而离散拓扑中单点 $\{r\}$ 是开集，所以这个重叠并非一条平面边界。

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

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

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