数学大学
C. Properties
计算几何 · 04. Voronoi Diagram
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
C. Properties
计算几何 · 04. Voronoi Diagram
Non-Empty Cells
每个站点的胞腔都非空：站点本身就在自己的胞腔里。
站点在内
站点到自己的距离为 0，最小
推论
n 个站点恰有 n 个非空胞腔
Empty Disks
空圆性质：Voronoi 边上的点能做出不含任何站点的空圆。
边上取圆心
以边上的点为心、到站点距离为半径作圆
内空
圆内不含任何站点，恰触两个或以上
Nearest = Concyclic
Voronoi 顶点 ⇔ 三站点共圆且该圆为空圆（最近站点恰为这三个）。
顶点刻画
顶点处的空圆恰触三个站点
退化
四站共圆时退化为四块胞腔交汇
Number of Nearest Sites
Voronoi 顶点的度数 = 空圆触到的站点数（一般情形为 3）。
度数三
一般位置下每个顶点恰好接三条边
退化
四站共圆时顶点度数为 4
Split & Merge
局部更新：新增或删除站点时，受影响的胞腔分裂或合并。
插入分裂
新站点的胞腔从邻近胞腔中切出
删除合并
删除站点的领地被邻站瓜分
本节要点
- ✓胞腔非空：站点总在自己领地内
- ✓空圆性质是 Voronoi 顶点的判据
- ✓顶点度数 = 最近站点数
延伸主题：为一条边构造空圆观察插入站点后的局部变化
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1空圆性质为什么等价于「Voronoi 边上的点」？
参考答案边上的点与两个站点等距，以此距离作圆恰好过这两个站点；圆内若有其他站点，该点就应属于那个站点的胞腔，矛盾。所以边上每点的以近邻为界的圆都是空圆，反之亦然。
2空圆性质如何用于「三点是否共圆」的判定？
参考答案三点总有外接圆，但只有当圆内没有其他站点时，三站的胞腔才交汇出一个 Voronoi 顶点。判断某顶点是否退化（度数 4）等价于检查空圆是否同时触到第四个站点。
3「删除站点」在实际系统中为什么比「插入」复杂？
参考答案删除后其胞腔成为无主之地，需要邻站瓜分——瓜分的边界不再只是相邻对的垂直平分线，可能是删除站点胞腔的多条边重组。插入只切一刀，删除要重分一大片。