数学大学
B. Terminologies
计算几何 · 04. Voronoi Diagram
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
B. Terminologies
计算几何 · 04. Voronoi Diagram
Site & Cell
站点与胞腔：站点是生成元，胞腔是该站点的最近邻统治区域。
站点
生成 Voronoi 图的输入点
胞腔
站点 p 的胞腔 = 所有离 p 最近的点集
Intersecting Halfspaces
代数视角：胞腔是 n−1 个「更近于 pᵢ」的半平面的交。
半平面交
每对站点贡献一个半平面约束
复杂度
n 个站点时胞腔至多 n−1 条边
Planar Voronoi Diagram
平面 Voronoi 图的整体结构：顶点、边、胞腔的计数关系欧拉公式可算。
顶点
Voronoi 顶点是三站点外接圆圆心
复杂度
n 站点的图至多 2n−5 个顶点、3n−6 条边
本节要点
- ✓站点生成胞腔，胞腔是最近邻区域
- ✓胞腔 = 半平面的交
- ✓结构复杂度线性于站点数
延伸主题：推导胞腔边数上界验证欧拉公式计数
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1Voronoi 顶点为什么会是三个站点的外接圆圆心？
参考答案Voronoi 顶点是三块胞腔的交汇处——到这三个站点距离相等的点。到三点等距的点恰是其外接圆圆心；若四站共圆则退化为四站点交汇（退化情形）。
2半平面交的视角对实现 Voronoi 有什么帮助？
参考答案它把「求一个胞腔」变成 n−1 次半平面交：每对站点贡献一条垂直平分线约束。单个胞腔可独立求解（O(n log n)），整个图则可用分治或扫描线一次建成 O(n log n)。
3胞腔可能是无界的吗？什么情况下发生？
参考答案会。位于站点集凸包边界上的站点，其胞腔向无穷延伸、无界。直觉：该方向之外没有其他站点「挡住」它的势力范围。内部站点的胞腔才是有界多边形。