问题背景
给定下面这个问题
假如你在城市里想找最近的邮局,怎么做最快?
这是一个经典的最近邻查询问题。几何化地说,给定平面上一组点,我们希望构造一个结构,能在查询时快速返回“离我最近的那个点”。这就是所谓的 Post Office Problem。然而,暴力搜索每次都遍历所有点,效率太低。我们需要一种预处理 + 快速查询的结构。
维诺图(Voronoi Diagram)
定义
- 设 为平面上的 个站点。
- 对于每个站点 ,其 Voronoi 单元(cell)定义为:
- Voronoi 图 是由所有 Voronoi 单元 对平面进行划分所得到的平面细分。
一些观察
共线退化
若所有站点共线,则 退化为 条平行直线(或平行带)。凸性
由半平面交集可得:其中 是以 为端点的垂直平分线所界定、包含 的开半平面。因此每个 Voronoi 单元都是凸的。
边与顶点
- Voronoi 边缘由相邻站点对的垂直平分线的段或半线组成,任一点落在边上时到两个站点距离相等。
- Voronoi 顶点是同时与至少三个站点等距的点,即空圆(圆心不含其他站点)的圆心。若站点处于一般位置(无四点共圆),则每个顶点恰由三个单元相交而成。
无界单元与凸包
仅当站点是凸包 的顶点时,其对应的 Voronoi 单元才是无界的;其余单元均为有界多边形。组合复杂度
对于 , 最多包含 条边和 个顶点,这一上界可由平面图的欧拉公式推得。
Fortune 算法
核心思想
Fortune 算法利用自上而下的平面扫描线(sweep line)思路,以 时间高效构造 Voronoi 图。扫描线算法的思想可以参考上一篇博客 「计算几何」扫描线算法与应用--线段交点问题。
如果观察 Voronoi 图的定义,当扫描线 从上向下移动到某个位置 时,任意点 的最近站点可能是已扫描的站点,也可能是尚未扫描到的站点。但只要 到已扫描站点 的距离 不大于它到扫描线的距离 ,即
那么 无论如何都比任何未扫描的站点更接近 ,其所属的 Voronoi 区域已经可以确定。满足该不等式的点集恰好是以 为准线的开口向下抛物线内部 。对所有已扫描站点分别得到这样的抛物线,抛物线的上包络即构成了“海滩线”(Beach Line),将平面分为“已定区”(海滩线以上)和“待定区”(海滩线以下);由于其形状酷似海岸线,故得名海滩线 。如下图所示,扫描线在当前位置时,海滩线(橙色曲线)之上区域的 Voronoi 归属已锁定,之下区域则需继续扫描新站点才能确定。
算法流程
事件列表如下:
- 站点事件(Site Event)
当 扫描到新站点 时,插入一个新的抛物线弧,将原有弧分裂为三段,生成新的断点并开始追踪对应 Voronoi 边 - 圆事件(Circle Event)
当三个相邻抛物线弧对应的站点共圆,最低点处触发圆事件。该事件导致中间弧消失,其消失位置即为一个 Voronoi 顶点 。
需要借助的数据结构如下:
- 事件队列 :按事件的 坐标排序,存储所有站点事件与待处理圆事件。
- 状态结构 :叶结点存储抛物线弧、内部结点存储断点;采用平衡二叉树,实现 的插入、删除和邻居查找 。
- DCEL(Doubly‐Connected Edge List):记录正在构造的 Voronoi 边和顶点,每个断点关联一条半边,事件发生时更新边表
因此,可以给出下面的代码伪代码:
VoronoiDiagram(P):
- 将所有站点按 y 坐标插入事件队列
- 初始化空状态结构 和空 DCEL
- while 非空 do:
- 从 中取出一个事件 e
- if e 是站点事件 :
- HandleSiteEvent()
- else:
- HandleCircleEvent()
HandleSiteEvent()
- 在 中查找垂直于 的弧 。若 曾登记圆事件,则将其移出 。
- 将 分裂成三段,新段属于 的抛物线插入中间,更新两侧断点并在 DCEL 中创建对应半边。
- 检测左右相邻三弧是否共圆,若是则将新圆事件加入 并建立指针。
HandleCircleEvent()
- 从 中删除对应弧 ,更新相邻断点位置。
- 移除所有与 相关的圆事件。
- 将圆心加入 DCEL 作为顶点,创建两条新半边并链接。
- 检测新相邻三弧是否生成圆事件,若是则插入 并建指针 。
复杂度分析
时间:共处理 次站点事件和 次圆事件,每次事件在 和 上做 操作,总耗时 。
空间: 均需 空间,总空间 。
参考资料
M. de Berg, O. Cheong, M. J. van Kreveld, and M. H. Overmars, Computational Geometry: Algorithms and Applications, 3rd ed. Berlin, Germany: Springer, 2008, ISBN 978-3-540-77973-5.