E. Euclidean Minimum Spanning Tree
数学大学
E. Euclidean Minimum Spa
计算几何 · 05. Delaunay Triangulation
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
E. Euclidean Minimum Spa
计算几何 · 05. Delaunay Triangulation
Definition
欧几里得最小生成树（EMST）：连接全部点、总边长最小的平面直线树。
目标
连接所有点的最小总欧氏长度
权
边的权即两端点的欧氏距离
Construction
构造方法：先建 Delaunay 图，再在图上跑 Kruskal/Prim。
两步法
Delaunay O(n log n) + 图上 MST O(n log n)
免全对
完全图有 O(n²) 条边，Delaunay 剪到线性
Subgraph of RNG
EMST ⊆ RNG ⊆ Gabriel ⊆ Delaunay：最小生成树藏在最稀疏的那一层。
包含
EMST 的每条边都在 RNG 中
利用
从 Delaunay 抽 RNG 再抽 MST，层层过滤
Example
例题：小点集上的 EMST 求解全流程演示。
流程
建 Delaunay → 抽边排序 → Kruskal 并查集选边
验证
结果树连通且总长最小
本节要点
- ✓EMST：总欧氏长度最小的连接树
- ✓Delaunay + Kruskal 两步构造
- ✓EMST ⊆ RNG ⊆ Gabriel ⊆ Delaunay
延伸主题：实现两步法 EMST比较 EMST 与最近邻路径
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1为什么 EMST 的边全部落在 Delaunay 图里？
参考答案MST 的每条边都是「相对邻域边」：不存在第三点使它比两端都近（否则换成更短的边可得更小的树，矛盾）。相对邻域边又在 RNG 中，而 RNG ⊆ Delaunay——链条完备。
2EMST 有什么典型工程应用？
参考答案聚类分析（单链接聚类的骨架）、网络布线（最短总线路）、图像分割（区域邻接的最小连接）与 TSP 近似（EMST 上做先序遍历可得 2 倍近似回路）。
3为什么先建 Delaunay 再抽 MST 比在完全图上跑 MST 更好？
参考答案完全图有 O(n²) 条边，Kruskal 排序就要 O(n² log n)；Delaunay 把候选边压到 O(n)，MST 降为 O(n log n)。剪枝的依据是 MST ⊆ Delaunay 的数学保证。