数学大学
G. Hardness
计算几何 · 04. Voronoi Diagram
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
G. Hardness
计算几何 · 04. Voronoi Diagram
1D Voronoi Diagram
一维 Voronoi 图：直线上的站点把直线切成若干区间，结构退化为点。
区间划分
相邻站点的中点即分界点
复杂度
n 个站点产生 n−1 个分界点
2D Voronoi Diagram
二维 Voronoi 图才是本课程的主场：胞腔为凸多边形，复杂度线性。
规模
至多 2n−5 个顶点、3n−6 条边
构造
可用分治、增量或扫描线方法构建
Voronoi Diagram In Gener
一般位置假设：无四站共圆、无三站共线——退化情形另行专门处理。
一般位置
顶点度数恰为 3 的干净结构
退化处理
共圆共线情形用符号扰动或显式分支
本节要点
- ✓一维退化为区间分界点
- ✓二维复杂度线性于站点数
- ✓一般位置假设简化主算法
延伸主题：画一维 Voronoi 图检查退化输入的处理路径
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1「一般位置假设」在算法教材中为什么被普遍采用？
参考答案退化情形（共圆、共线、重合）会让分支爆炸、代码膨胀，而真实数据极少落在精确退化上。主算法在一般位置下最简洁，退化用扰动或专门分支收尾——关注主要矛盾。
2一维 Voronoi 图为什么只是「分界点集合」而二维才是图？
参考答案一维的胞腔是区间、分界是孤立的点，没有边与顶点构成的图结构；二维的胞腔是多边形、边界交织成真正的平面图。维度决定结构丰富度。
3「退化输入」在 Voronoi 中具体指哪些情形？
参考答案四点共圆（顶点度数 4）、三点共线（无穷长边方向重合）、站点重合（胞腔共享）。这些情形会让主算法的假设失效，通常用符号扰动把退化输入「推」成一般位置再处理。