数学大学
A. Introduction
计算几何 · 04. Voronoi Diagram
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
A. Introduction
计算几何 · 04. Voronoi Diagram
A First Glance
Voronoi 图初见：按「离谁最近」把平面划成势力范围的空间划分。
划分
每个站点统治离它最近的区域
边界
相邻势力的分界是垂直平分线
Dining Halls on Campus
校园食堂例子：每个学生去最近的食堂——食堂的势力范围就是 Voronoi 胞腔。
建模
食堂为站点，学生位置查询所属胞腔
应用问题
新食堂选址即求最大空圆问题
More Analogies & Applica
更多类比与应用：基站覆盖、天气预报分区、 nearest-neighbor 检索。
覆盖
基站服务范围按 Voronoi 划分
检索
最近邻查询沿 Delaunay 图跳转
Voronoi
Voronoi 图的正式名字来源：俄国数学家 Georgy Voronoy。
别名
泰森多边形、Dirichlet 划分
对偶
其对偶是站点集的 Delaunay 三角剖分
本节要点
- ✓Voronoi：按最近站点划分平面
- ✓食堂与基站是最直观的应用
- ✓对偶结构是 Delaunay 三角剖分
延伸主题：手画三站点的 Voronoi 图思考新增站点的边界变化
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1为什么 Voronoi 胞腔一定是凸的？
参考答案每个胞腔是一组「离本站更近」的半平面约束之交：每对站点的垂直平分线切出一个半平面。凸集之交仍是凸集，故胞腔必为凸多边形（可能无界）。
2Voronoi 图在「新增一个站点」时会如何变化？
参考答案新站点的胞腔从周围胞腔中「切割」出来：以新站点为圆心，附近胞腔被其对应的若干垂直平分线切走一块。受影响的只有新站点邻近的胞腔，其余区域纹丝不动——局部性是 Voronoi 图的重要性质。
3「最大空圆」问题为什么在 Voronoi 顶点上取最优？
参考答案最大空圆的圆心要离所有站点尽量远。把圆心从 Voronoi 顶点向任何方向移动都会接近某个站点；候选圆心只需在 Voronoi 顶点与区域边界上找，其中顶点处的空圆最大。