沃罗诺伊图将空间划分为若干区域,每个区域对应于一组称为站点的对象中的一个。每个区域由到其对应站点的距离不大于到任何其他站点距离的所有位置组成。在标准形式中,站点是平面上的点,远近以通常的欧几里得距离衡量。由此得到的是由凸多边形区域拼合而成的划分,其中一些区域向无穷远延伸。更一般的构造则采用不同的距离度量、带权站点、曲线、曲面或更高维的空间。
沃罗诺伊图将“哪个站点最近?”这一问题转化为一种几何结构。其边界标示出最近站点归属发生变化的位置,而其顶点则对应于多个站点并列最近的位置。这些性质使沃罗诺伊图成为计算几何中的基本结构,并广泛应用于空间分析、科学计算、材料建模和数据分析。沃罗诺伊图与德劳内三角剖分之间的关系,将最近邻几何与网格生成、插值以及空圆和空球的几何性质联系起来。
定义与初等几何
设 是 欧几里得空间 中由互不相同的种子点组成的有限集合。属于 的闭沃罗诺伊单元定义为
这些单元共同覆盖整个空间。它们的内部互不相交,但边界可以重合,因为边界上的点可能与两个或更多种子点等距,且这些种子点都是离它最近的。因此,这里的“划分”通常取几何意义,而不是指各部分严格互不相交的集合划分。如果要求每个点只能归属一个单元,可以预先规定等距时的归属规则,将边界点分配给各个单元。
两个种子点所对应区域之间的边界位于这两个点的垂直平分线上。将距离的平方展开可得
因此,每一次两两比较都定义了一个闭半空间,而一个单元就是这些半空间的交集。由此可知,普通欧几里得点种子模型中的每个单元都是凸集。在二维空间中,它是一个可能无界的凸多边形;在三维空间中,它是一个可能无界的凸多面体。每个种子点都严格位于自己的单元内部,因为它到自身的距离为零,而其他种子点都与它不同。
例如,考虑种子点 、 和 。 的单元是满足 、 的区域。 的单元满足 和 ,而 的单元满足 和 。三个单元都在 处相交,该点是这三个种子点所构成三角形的外心。虽然三条两两垂直平分线都是完整的直线,但只有其中适当的部分属于沃罗诺伊图:在其余部分上,第三个种子点的距离更近。
在非退化的平面沃罗诺伊图中,一条边由恰好有两个最近种子点的点组成,而一个顶点恰好有三个最近种子点。如果四个或更多种子点共圆,则可能产生一个与四个或更多单元相接的顶点。一个单元无界,当且仅当它的种子点位于所有种子点的凸包边界上。种子点共线时,得到的图尤其简单,由若干平行条带和最外侧的两个半平面组成,没有有限位置的沃罗诺伊顶点。
实际应用中,经常将沃罗诺伊图限制在一个有界的研究区域 内,用 代替每个单元。这种操作称为裁剪或限制。凸的研究区域能够保持单元的凸性,而非凸区域则可能将限制后的单元分割成互不连通的部分。裁剪所引入的边界来自研究区域,而非最近种子点关系本身所决定的几何结构。
德劳内对偶与高维结构
最重要的伴随结构是德劳内三角剖分。对于处于一般位置的平面站点,两个站点之间存在一条德劳内边,当且仅当它们的沃罗诺伊单元共享一条边。每个沃罗诺伊顶点都对应一个德劳内三角形,该三角形的外心就是这个顶点。这是一种几何对偶:站点对应于单元,德劳内边对应于沃罗诺伊边,德劳内三角形对应于沃罗诺伊顶点。
德劳内三角形的定义性质是,其外接圆的开圆盘内不含任何站点。在对应的沃罗诺伊顶点处,到这三个站点的距离相等,且不存在更近的其他站点。反过来,经过三个站点的空圆,如果圆周上没有其他站点,就确定了一个沃罗诺伊顶点。连接两个相邻站点的德劳内边与对应的沃罗诺伊边垂直,但两者的有限线段部分未必相交。特别地,钝角德劳内三角形的外心位于三角形之外。
一般位置假设使这一对偶结构成为无歧义的三角剖分。如果四个站点位于同一个空圆上,它们的沃罗诺伊单元就可能交于同一个顶点,对应的德劳内面则是一个四边形。选取任意一条对角线都可以将该面剖分为三角形,同时保持开圆盘内无站点的性质。因此,更本质的对象是德劳内细分;将其中的非单纯形面进一步剖分,便可得到三角剖分。尽管底层的沃罗诺伊图不变,但在比较组合结构的软件中,对角线的任意选择仍可能影响结果。
平面性严格限制了二维沃罗诺伊图的规模。对于 个不全共线的站点,若任意四点不共圆,且有 个站点位于凸包边界上,则有限沃罗诺伊顶点数和沃罗诺伊边数分别为
这里的边包括无界射线。这些公式可由与欧拉示性数有关的平面计数关系,以及一般位置下德劳内三角剖分的有界面均为三角形这一事实推导出来。特别地,平面沃罗诺伊图的组合复杂度是线性的。
一种有用的高维解释是,将每个站点 提升到抛物面上:
将提升后的点集的凸包下表面上的各个面投影回原空间,即可得到德劳内细分。这将最近站点几何与凸包算法联系起来,也解释了为什么在高维空间中,空球取代了空圆。平面情形下良好的规模上界并不能延续到高维:对于固定维数 ,最坏情况下的组合复杂度可达到 。即使在三维空间中,复杂度也可能达到二次量级,因此,即便单次最近邻查询尚可高效处理,构建完整的沃罗诺伊图仍可能代价高昂。
历史发展
这种构造的出现早于其现代名称。勒内·笛卡尔于1644年出版的《哲学原理》以涡旋理论解释物质,其中描绘了围绕各个中心、填满空间的区域。这些图示常被视为类似沃罗诺伊划分的早期雏形。不过,它们并非关于最近站点单元的现代数学理论,应当将这种外观上的相似与后来基于距离的精确定义区分开来。
狄利克雷于1850年的研究对这一构造作出了直接的数学论述。在研究二次型时,狄利克雷考察了由与格点的远近关系所确定的区域。格在平移下呈周期性重复,因此,各格点的最近点区域都是同一个基本单元的平移副本。这一背景将这种构造与数论和数的几何联系起来,而非与现代空间计算中常见的不规则有限点集联系起来。“狄利克雷域”这一名称至今仍是几何学若干分支中的标准术语。
格奥尔基·沃罗诺伊在1908年发表的研究中进一步发展了这一理论,尤其是在高维格与二次型分类方面。他的名字后来被用于指称更广义的最近站点构造,英语中通常拼作“Voronoi”。由于转写方式不一,历史和数学文献中也会出现“Voronoy”这一拼法。尽管现代教材通常从平面情形介绍沃罗诺伊图,但使其得名的核心研究所涉及的数学背景要广泛得多。
气象学中独立出现了一项影响深远的应用。1911年,阿尔弗雷德·H.·泰森提出了一种估算某一区域平均降水量的方法:将多边形区域分配给各个雨量站。每个雨量站代表研究区域中距该站比距其他任何雨量站都近的部分。由此得到的面积加权平均方法后来被称为泰森多边形法。这项应用确立了一套实用术语,至今仍广泛用于水文学和地理信息系统,尽管其背后的几何结构与普通的平面沃罗诺伊图完全相同。
鲍里斯·德洛内于1934年的研究确立了如今以其名字命名的空球剖分,使对偶关系成为这一领域的核心内容。20世纪70年代和80年代,计算几何将这些构造发展为标准的算法研究对象。迈克尔·沙莫斯与丹·霍伊于1975年提出了一种影响深远的平面分治方法;史蒂文·福琼于1987年发表的论文则引入了广泛使用的扫描线算法。此后的发展重点包括稳健的几何判定、加权与高维变体、动态更新以及大规模实现。这些进展将源自二次型、空间测量和离散几何的数学传统汇聚到了一起。
构造算法与数值稳健性
从半空间定义可以直接得到一种构造方法:对于每个生成点,从整个空间或一个有界区域开始,依次与其余各生成点所确定的半空间求交。这种方法概念清晰,适用于输入规模较小或需要裁剪单元的情况。不过,它需要在所有生成点之间进行平方量级的两两比较,而直接进行多边形裁剪还可能带来额外的计算开销。更精巧的平面算法利用最终图的规模为线性这一特点,可以达到 的时间复杂度,这里使用的是标准的大O记号。
分治算法先对生成点排序,将其分成两组,递归构造各组的沃罗诺伊图,再沿一条分界线合并两图;这条分界线将更靠近左侧点组的区域与更靠近右侧点组的区域分隔开。如果合并可在线性时间内完成,就有递推式 ,从而得到 的时间复杂度。另一种方法是先构造德劳内三角剖分,再以三角形的外心作为沃罗诺伊顶点,并根据相邻三角形构造沃罗诺伊边。当软件系统已经维护着一个三角剖分时,这种利用对偶关系的途径尤其方便。
Fortune算法用一条直线扫过平面。在已处理的生成点与扫描线之间,有一条由抛物线弧组成的“海滩线”:每段弧上的点到某个生成点与到当前扫描线的距离相等。遇到新的生成点时,生成点事件会引入新的弧段;到达一个潜在的沃罗诺伊顶点时,圆事件会移除弧段。算法用平衡搜索结构维护海滩线,并用优先队列维护事件。在通常的计算假设下,该算法的时间复杂度为 ,空间复杂度为 。由于后续的生成点事件可能改变海滩线的局部结构,因此必须检测出已经失效的圆事件。
随机增量方法是另一类重要方法。它按随机顺序插入生成点,并更新沃罗诺伊图或三角剖分中受影响的部分。借助适当的点定位结构和历史记录结构,平面德劳内三角剖分的构造可以达到 的期望时间复杂度。对于典型数据,动态插入通常只涉及局部修改,但在最坏情况下,一次更新可能影响许多单元。删除操作则更为复杂,因为必须根据邻近生成点,重建此前由被删除生成点所占据的区域。
可靠的实现必须将组合结构上的判定与近似坐标计算区分开来。方向测试用于判断一个点位于某条直线的哪一侧;圆内测试用于判断一个点是否位于某个外接圆内部。两者都可以用行列式表示。对于近乎共线或近乎共圆的数据,普通的浮点运算可能给出错误的符号,导致邻接关系不一致或拓扑结构无效。精确谓词、自适应精度运算和一致的符号扰动可以解决这些问题。然而,精确的判定并不会自动保证计算出的外心坐标准确:三个近乎共线的点,其外心可能极为遥远,而且对数值误差十分敏感。因此,退化情形的处理与坐标准确性是相互关联但又有所区别的实现问题。
其他距离、权重与站点
最近站点的定义可以自然地推广到度量空间 :
图的几何形态在很大程度上取决于所采用的距离。在曼哈顿距离 下,最短路径体现了沿各坐标方向移动的方式,等距分界线则是分段线性的。在最大坐标距离 下,二维空间中的度量球是边与坐标轴平行的正方形。与欧几里得距离的情形不同,某些非严格凸的度量允许两个不同站点之间的等距区域具有非空内部。因此,如何处理等距情形,影响的可能不只是边界曲线。
一种特别实用的加权构造是幂图。为站点 赋予实数权重 ,并比较幂值
站点 的胞元由使 取得最小值的点组成。两个幂值相等的条件仍可化为线性方程,因此幂胞元仍然是凸多面体。加权站点的胞元可能为空,也不一定包含该站点本身。若 ,这一幂表达式还具有经典的几何含义,即一个点相对于半径为 的球的幂。其对偶结构称为正则三角剖分。
其他加权方式会产生不同的图。加性距离权重比较的是 ;在平面上,其等距分界线通常是双曲线。乘性权重比较的是 ,其中 ;其等距分界线通常是圆或直线,胞元则不一定是凸的,也不一定连通。这些模型不能仅靠重新标记权重就替代幂图。每种加权方式都表达了不同的机制,例如初始时间优势、传播速度,或基于距离平方的偏好。
站点不一定是点。到线段、多边形或曲面的距离,通常定义为到该对象上任意一点的距离的最小值。线段的沃罗诺伊图既包含曲边,也包含直边。多边形的中轴与此密切相关:它由多边形内部具有多个最近边界点的位置组成,也可以用极大内切圆的圆心来刻画。以线段为站点构造沃罗诺伊图,可以用来计算这类骨架表示,但需要对边界特征和端点作特殊处理。
还有一些变体会改变查询方式或所在空间。 阶图记录的是最近的 个站点组成的集合,而不只是最近的一个站点。最远站点图选择使距离达到最大的站点,并且只取决于凸包上的站点。测地沃罗诺伊图使用绕过障碍物或沿曲面行进的最短路径距离;网络沃罗诺伊图则使用图上的最短路径。在这些情形中,欧几里得距离下的直线边界和凸性通常不再成立。这些图的实用价值,恰恰在于能够表示普通平面距离所忽略的移动约束或曲面几何。
随机剖分与空间统计
当生成点随机分布时,其沃罗诺伊图就成为一个随机几何对象。研究最充分的模型采用强度为 的齐次泊松过程:面积为 的区域内,生成点的数量服从均值为 的泊松分布,且互不相交区域内的点数相互独立。在无限平面上,这会形成平稳、各向同性的泊松–沃罗诺伊剖分。其统计特征可用于模拟不规则的空间竞争,而无须预设底层网格。
泊松模型可以直接导出若干有用的量。若 表示某个固定位置到最近生成点的距离,那么 当且仅当以该位置为圆心、半径为 的圆盘内没有生成点。因此,
且
这些公式描述的是独立选取的位置到最近生成点的距离,而不是某个生成点到其单元内各点的距离。将长度乘以 进行缩放,即可消去强度参数,因此许多无量纲的形状统计量与 无关。
通过典型生成点选出的典型单元,其平均面积为 。在平面泊松–沃罗诺伊模型中,单元的平均边数为六。这一结果反映了平面上的关联关系,以及每个顶点几乎必然恰有三个单元相交这一事实。但这并不意味着该剖分主要由正六边形铺砌而成:各个单元的面积、边数、狭长程度和边长都存在很大差异。许多统计量的完整分布,包括单元面积分布,都没有同样简单的闭式表达式,需要借助界限、近似和模拟来研究。
典型单元与包含均匀抽样位置的单元之间存在一个关键区别。后一种抽样方式更容易选中较大的单元,因为它们占据的面积更大。因此,与按典型生成点选取的单元分布相比,这种分布带有面积偏倚。混淆这两种抽样方案,可能会导致对平均辖域大小或典型空间体验作出错误判断。这一区别体现了统计学中一个更普遍的问题:观测方式会改变所测量的分布。
对观测到的剖分,还需要谨慎处理边界。与观测窗口边缘相交的单元只能被部分观测到;若将其裁剪后的面积当作完整面积,就会使形状和大小的统计汇总产生偏倚。周期性边界条件、缓冲区域或适当的边缘校正,可分别应对这一问题的不同情形。偏离泊松模型的现象也能提供有用信息:具有排斥性的生成点过程往往产生更规则的单元,而聚集过程则会形成密集的小单元与大片稀疏区域并存的格局。沃罗诺伊统计量可以量化这些模式,但仅凭拟合得到的剖分,无法确定产生这些模式的物理过程。
质心沃罗诺伊图、聚类与量化
质心沃罗诺伊镶嵌是一种沃罗诺伊图,其中每个生成点都与其自身单元按指定密度计算的质心重合。对于有界区域 和非负密度 ,定义
这一能量衡量用最近的生成点代表每个位置时产生的总平方误差。密度可以表示人口、采样重要性或其他空间权重,而不一定表示物理质量。
质心条件可由两个相互补充的最小化过程导出。生成点固定时,将每个点分配给最近的生成点,可使该点对平方距离的贡献最小。区域固定时,各区域的最优代表点则是其加权质心:
前提是分母为正。因此,在适当的正则性假设下,驻点构型满足质心条件。它不一定是全局最小值点,而且不同驻点构型的能量可能不同。
劳埃德算法交替执行这两个步骤:先构造沃罗诺伊单元,再将每个生成点移动到其单元的质心。每一步若精确执行,都不会增加平方距离能量。该方法源于斯图尔特·劳埃德于1957年在贝尔实验室开展的最小二乘量化研究,相关成果于1982年发表。其离散形式就是用于K均值聚类的标准劳埃德迭代:将数据点分配给最近的聚类中心,再以各簇的均值替换原有中心。空簇的均值没有定义,因此需要另行规定处理方式。
同样的数学原理也是矢量量化的基础。有限码本用于表示连续或高分辨率的信号空间;编码时选择最近的码字,每个码字的判决区域就是一个沃罗诺伊单元。在采用平方欧几里得距离的损失函数下,最小化期望失真可得到质心条件。改变失真度量会改变判决区域及最优更新规则,因此并非所有量化器都能用普通的欧几里得质心沃罗诺伊图来描述。
当平面密度均匀、生成点众多且远离边界时,低能量构型通常会趋近于局部六边形图案。生成点按三角晶格排列时,会形成正六边形沃罗诺伊单元,实现高效且近乎各向同性的覆盖。但这一现象并不能证明,对于任意区域、有限生成点数量、密度或维数,六边形都具有普遍的最优性。边界及随空间变化的密度会引入缺陷,并导致单元大小不一。在维数为 的高分辨率平方误差模型中,渐近最优的生成点密度与 成正比,而非直接与 成正比。重要性较高的区域会获得更多代表点,但这种分配也反映了单元变小时近似误差的下降规律。
最近种子点模型的应用与局限
在地理信息系统中,沃罗诺伊单元可用来划定服务范围、邻近区域和空间聚合单元。泰森多边形法的降雨量估计为
其中, 是雨量站 测得的降水量, 是该站对应单元位于流域内的面积。这种方法将每个位置的取值设为最近雨量站的观测值。因此,它是一种分片常数空间模型,而不是对大气动力过程或地形效应的重建。设施分析中也有类似的分配方式,但直线距离上的邻近关系未必能反映出行时间、服务容量或实际使用情况。
沃罗诺伊几何也可用于更平滑的插值。在自然邻点插值中,将查询点临时加入种子点集。新生成的沃罗诺伊单元会从相邻单元中占取部分面积,再以这些被占取的面积确定相邻种子点数据值的权重。由此得到的局部插值模型,其邻域会随种子点的空间布局而调整。这与仅采用最近观测值的做法有本质区别,但仍利用同一种几何结构来识别相关邻点。
在科学计算中,配对的德劳内网格与沃罗诺伊网格可用于有限体积法。沃罗诺伊单元充当控制体,而相邻种子点之间的连线垂直于它们的公共面。对于各向同性扩散,这种正交性使得法向通量可以用简单的两点格式近似。在公共面上采用大小相等、方向相反的通量,即可保证守恒。对于强各向异性扩散、复杂边界或破坏正交性的网格修改,则需要更精细的离散格式;仅凭沃罗诺伊几何,并不能保证对所有微分方程都具有准确性或稳定性。
在材料建模中,种子点可以代表形核中心。如果所有中心同时出现,并在均匀介质中以相同速度各向同性地生长,那么各中心最先到达的区域就是普通的沃罗诺伊单元。形核时间或生长速度不同,则会得到加权或其他广义形式的构造。在原子尺度分析中,三维单元用于描述局部环境和配位情况,而幂图可将粒子尺寸差异纳入考虑。不过,沃罗诺伊邻点只是几何意义上的邻点,并不自动意味着存在化学键;微小的面以及扰动都可能改变推断出的配位关系。
机器人技术利用沃罗诺伊边规划路线,以兼顾与附近各障碍物的距离。对于多边形障碍物,广义沃罗诺伊图和中轴构造可以识别局部净空较大的通道。具有实际尺寸的机器人需要适当的自由空间表示,通常先对障碍物进行膨胀,再规划路径。同时,计算机图形学利用最近种子点距离场生成胞状纹理、程序化石纹、类似断裂的区域划分,并进行空间采样。视觉上呈胞状的图案,并不一定意味着其背后存在生成沃罗诺伊结构的物理过程。
在数据检索中,沃罗诺伊图是最近邻分类的几何决策分区图,但通常不必显式构造它。树结构索引、近似搜索和直接距离计算可能是更合适的选择,尤其是在受到维数灾难影响时。纵观这些应用,建模时的关键问题在于“最近”的含义:欧氏距离、出行成本、加权到达时间以及特征空间中的相似性,会定义不同的分配方式,也对应不同的解释。