数学大学
I. VD_sorted
计算几何 · 04. Voronoi Diagram
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
I. VD_sorted
计算几何 · 04. Voronoi Diagram
ε-Closeness
ε 接近：考察「距离在 ε 以内」的近邻关系，为 VD 排序的转化做铺垫。
定义
两站点距离不超过 ε 视为接近
与排序
排序是按数轴位置比较，非近邻关系
Lifting
提升：把平面点 (x,y) 抬到抛物面 (x,y,x²+y²) 上，联系最近邻与排序。
抛物面
z=x²+y²，提升后距离产生加权效果
作用
让 VD 的近邻编码出 x 方向的次序信息
Projection
投影回平面：从提升后的结构读出关于原点排序的信息片段。
读片段
只能读出局部次序信息，不是完整排序
Case A
情形 A：站点恰在数轴上时，一维 Voronoi 分界点直接给出排序。
一维退化
Voronoi 退化为中点分界，天然有序
Case B
情形 B：一般平面站点时，Voronoi 不保留 x 次序，归约失败。
次序丢失
近邻关系与 x 大小没有必然联系
结论
VD 不能免费给出排序
Sorting Not Made Easier
结论：用 Voronoi 图做排序并不会更简单——下界依旧，归约走不通。
失败教训
归约需要精心构造，而非任意尝试
对照
凸包的归约成立，因为 x 单调映射到位置
本节要点
- ✓尝试用 VD 排序：提升 + 投影
- ✓一维可行，二维平面站点失败
- ✓结论：排序不会因 VD 变简单
延伸主题：复盘归约失败的原因复习凸包下界的成功归约
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1为什么「凸包能排序」成立而「Voronoi 能排序」失败？
参考答案凸包归约用的映射 (aᵢ,aᵢ²) 把数的大小单调映射为边界位置，凸包遍历天然按次序给出结果；Voronoi 的近邻关系与坐标大小无关，平面站点的胞腔邻接不保序。归约成败在于映射是否保序。
2这个失败的归约尝试有什么正面价值？
参考答案它精确划定了 Voronoi 图的能力边界：近邻结构 ≠ 序结构。理解「什么归约不成立」与「什么成立」同样重要——防止未来在错误方向上浪费设计精力。
3情形 A 中一维 Voronoi 为什么能直接给出排序？
参考答案一维站点的 Voronoi 图退化为数轴上的分界点（相邻站点中点），从左到右遍历分界点之间的区间，站点天然按坐标排序——近邻结构在低维退化时与序结构重合。