沃罗诺伊图

沃罗诺伊图（Voronoi diagram）按照最近的给定站点，把空间分成若干区域。例如三处服务站位于 $A=(0,0),B=(4,0),C=(0,4)$，若服务代价是直线距离，位置 $(3,1)$ 应归给 B，因为到三站的距离平方依次为十、二、十八。整张图一次描述所有查询位置的最近站点。

图只截取一个观察窗口。三块区域实际向无穷远延伸，窗口边框不是沃罗诺伊边。

最近区域与平局边界

本文讨论平面欧氏距离，站点集 $P=\{p_1,\dots ,p_n\}$ 有限、非空，站点两两不同。采用包含平局边界的闭区域约定： $$V_i=\{x\in {ℝ}^2:\Vert x-p_i\Vert \le \Vert x-p_j\Vert \text{ 对每个 }j\}.$$ 有限个距离一定有最小值，所以这些区域覆盖整个平面。不同区域可以共享边或顶点；若需要每个查询只返回一个站点，可另外按站点编号打破平局。平局处理不是把共享边从几何图中删除。也有教材先用严格不等式定义开放的单元，再取闭包构成图；两种写法须辨明。

两站点 p、q 的比较可以去掉平方根。展开平方并消去 $\Vert x{\Vert }^2$，得到 $$\Vert x-p{\Vert }^2\le \Vert x-q{\Vert }^2⟺2(q-p)\cdot x\le \Vert q{\Vert }^2-\Vert p{\Vert }^2.$$ 右侧是闭半平面，边界是 pq 的垂直平分线。因此 $V_i$ 是所有这些半平面的交，是可能无界的凸多边形区域。其凸性也可直接证明：若 x、y 满足每一个线性不等式，则 $tx+(1-t)y$ 对 $0\le t\le 1$ 仍满足它们。相反，单个点若违反某一条比较，就有另一个站点更近，不能留在该单元中。这证明了半平面交与最近区域完全相同。

每个站点自身严格近于其他站点，故其附近有一小片区域只属于它。两个不同单元的交则必须满足两站点等距，因而位于一条直线上，不能有二维内部。这里“内部不交”和“闭区域完全不交”是不同断言。

三站点图的逐项构造

对主例，A 与 B 比较给出 $x\le 2$，A 与 C 比较给出 $y\le 2$。B 与 C 比较给出 $x\ge y$。所以 $$V_A=\{x\le 2,y\le 2\},V_B=\{x\ge 2,x\ge y\},V_C=\{y\ge 2,y\ge x\}.$$ AB 两区真正共享的边是射线 $x=2,y\le 2$，不是整条垂直平分线；超出 y=2 后 C 比它们都近。同理，AC 边为 $y=2,x\le 2$，BC 边为 $x=y\ge 2$。三边交于 $(2,2)$，到三站距离均为 $\sqrt{8}$，它是三角形 ABC 的外心。

查询点 $(2,1)$ 到 A、B 的距离平方都为五，到 C 为十三，故落在 AB 共享边上；这正是平局边界的意义。单站点时没有比较条件，其区域是整个平面；只有两个不同站点时，一条垂直平分线把平面分为两个闭半平面。

增加第四站点的变式

加入 $D=(4,4)$ 后，四站构成正方形。A 区仍为 $x\le 2,y\le 2$，B 区改为 $x\ge 2,y\le 2$，C 区为 $x\le 2,y\ge 2$，D 区为 $x\ge 2,y\ge 2$。可以分别代回六组距离比较核验。旧的 BC 斜射线消失，被上方和右方的新边代替；不是把 D 周围随意画一个圆。

四个闭区域在同一点相遇。B 与 C 只共享该点，没有共享一条边。

四站共圆使同一个顶点对应四个最近站点。因此“每个沃罗诺伊顶点恰连三条边”需要一般位置条件，不能用于这个变式。它也解释了与德劳内三角剖分的对偶关系为什么要注意退化情形：单元共享一条边与仅共享一个点，含义不同。

距离模型的限制

上述直线边界与凸性来自欧氏距离平方的消去。若服务时间受道路、河流或不同通行速度影响，直线最近站点可能不是最快站点，必须先改变距离模型。加权站点、最远点、线段站点也有各自的沃罗诺伊结构，不能把本篇公式直接照搬。

重合站点会给出完全相同的距离函数，两个闭区域也完全重合，破坏前面“不同单元内部不交”的结论，所以须先合并或另设标签规则。实际绘图常把无界区域裁到矩形或研究区内；裁切边界来自展示或应用范围，不是站点之间的等距边。构图与查询也不同：即使尚未建立区域，逐个比较 n 个距离仍可准确回答单个最近邻查询。