E. Representation
数学大学
E. Representation
计算几何 · 04. Voronoi Diagram
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
E. Representation
计算几何 · 04. Voronoi Diagram
Subdivision
Voronoi 图是一种平面细分（subdivision）：顶点、边、面有清晰的层级结构。
结构层级
胞腔为面，分界线段为边，交汇点为顶点
遍历友好
细分结构支持系统化的面与边遍历
Fary's Theorem
Fary 定理：任何平面图都能直线画在平面上不交叉——Voronoi 边因此可以全是直线段。
直线化
平面图存在直线嵌入
与 Voronoi
Voronoi 边本是直线或折线，符合定理
Representing VD
存储 Voronoi 图：边表不足以支持邻接查询，需要半边结构（DCEL）。
记录内容
顶点坐标、边的两端点与左右面、边的前后继
查询需求
面→边→邻面的遍历与点的定位都要 O(度数)
本节要点
- ✓Voronoi 图是标准平面细分
- ✓Fary 定理保证直线嵌入
- ✓存储需半边结构支持邻接遍历
延伸主题：设计 Voronoi 图的存储结构实现一次面遍历
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1为什么简单的「边列表」不足以表示 Voronoi 图？
参考答案边列表只能回答「这条边连接哪两个顶点」，无法回答「这条边两侧是哪两个胞腔」「绕某个胞腔一圈有哪些边」。应用恰恰需要这些邻接与面信息，所以必须用半边类结构。
2Fary 定理对 Voronoi 图的可读性意味着什么？
参考答案Voronoi 边可以全部画成直线段而不会交叉——可视化时无需折线绕行。同时直线边让「点到边的距离」「边与查询点的位置关系」等计算简单稳定。
3Fary 定理的证明思路对「直线化」有什么启示？
参考答案证明采用归纳：逐步把折线边替换为直线边而不引入交叉。启示是「平面图的结构灵活性」——交叉自由度足够大，总能找到无交叉的直线摆法，Voronoi 图正受惠于此。