Euclidean MST
平面点集的完全图边权为欧氏距离;用 Delaunay 三角剖分 + Kruskal 在 O(n log n) 时间求 MST。标签 生成树 / 计算几何 / 欧氏距离 / Delaunay
题目描述
给定平面上的 个点 。在完全图上定义边权为两点间的欧氏距离
记 为两点间的欧氏距离。求该图最小生成树的权值和。
题解
完全图有 条边。 较小时,直接在完全图上跑 Prim 即可,时间 、空间 。
二维可以利用 Delaunay 三角剖分。记点集的 Delaunay 边集为 。核心事实是:EMST 的每条边都属于 。
设 是某棵 EMST 的边。删去 后树分成两个连通块 。若存在点 同时满足
则 必在 或 中。若 ,边 横跨这个割且比 短;若 ,边 同理,均与 是 MST 边矛盾。因此以 为直径的圆内没有其它点, 是 Delaunay 边。
于是算法为:
- 构造点集的二维 Delaunay 三角剖分;
- 只保留剖分中的 条边;
- 对这些边跑 Kruskal。
二维 Delaunay 可以在 时间构造。
复杂度
构造 Delaunay 为 ,对其 条边排序并跑 Kruskal 也是 ,总复杂度 ,空间 。最近点对给出 下界,因此这个复杂度在代数决策树模型下最优。
实现提示
- 二维的核心是 Delaunay 构造;坐标为整数时,要处理共圆、共线、重复点,最好使用稳健的几何谓词或符号扰动。
- 若 较小,直接写 Prim 的 往往比实现 Delaunay 更简单。
- Delaunay 的边数为 ,所以后续 Kruskal 的瓶颈仍是排序,整体保持 。