Euclidean MST

平面点集的完全图边权为欧氏距离;用 Delaunay 三角剖分 + Kruskal 在 O(n log n) 时间求 MST。

标签 生成树 / 计算几何 / 欧氏距离 / Delaunay

题目描述

给定平面上的 𝑛 个点 𝑝𝑖=(𝑥𝑖,𝑦𝑖)。在完全图上定义边权为两点间的欧氏距离

𝑤(𝑖,𝑗)=(𝑥𝑖−𝑥𝑗)2+(𝑦𝑖−𝑦𝑗)2

记 𝑑(𝑎,𝑏) 为两点间的欧氏距离。求该图最小生成树的权值和。

题解

完全图有 𝑂(𝑛2) 条边。𝑛 较小时,直接在完全图上跑 Prim 即可,时间 𝑂(𝑛2)、空间 𝑂(𝑛)。

二维可以利用 Delaunay 三角剖分。记点集的 Delaunay 边集为 𝐷(𝑃)。核心事实是:EMST 的每条边都属于 𝐷(𝑃)。

设 𝑝𝑞 是某棵 EMST 的边。删去 𝑝𝑞 后树分成两个连通块 𝐴,𝐵。若存在点 𝑟 同时满足

𝑑(𝑝,𝑟)<𝑑(𝑝,𝑞),𝑑(𝑟,𝑞)<𝑑(𝑝,𝑞)

则 𝑟 必在 𝐴 或 𝐵 中。若 𝑟∈𝐴,边 𝑟𝑞 横跨这个割且比 𝑝𝑞 短;若 𝑟∈𝐵,边 𝑝𝑟 同理,均与 𝑝𝑞 是 MST 边矛盾。因此以 𝑝𝑞 为直径的圆内没有其它点,𝑝𝑞 是 Delaunay 边。

于是算法为:

  1. 构造点集的二维 Delaunay 三角剖分;
  2. 只保留剖分中的 𝑂(𝑛) 条边;
  3. 对这些边跑 Kruskal。

二维 Delaunay 可以在 𝑂(𝑛log𝑛) 时间构造。

复杂度

构造 Delaunay 为 𝑂(𝑛log𝑛),对其 𝑂(𝑛) 条边排序并跑 Kruskal 也是 𝑂(𝑛log𝑛),总复杂度 𝑂(𝑛log𝑛),空间 𝑂(𝑛)。最近点对给出 Ω(𝑛log𝑛) 下界,因此这个复杂度在代数决策树模型下最优。

实现提示

  • 二维的核心是 Delaunay 构造;坐标为整数时,要处理共圆、共线、重复点,最好使用稳健的几何谓词或符号扰动。
  • 若 𝑛 较小,直接写 Prim 的 𝑂(𝑛2) 往往比实现 Delaunay 更简单。
  • Delaunay 的边数为 𝑂(𝑛),所以后续 Kruskal 的瓶颈仍是排序,整体保持 𝑂(𝑛log𝑛)。
源码位置