KACTL 算法笔记

036-几何-曼哈顿最小生成树

6 min read

  1. YAML 元数据 已设置 tags: [KACTL, 几何, 核心实体]。

  2. 核心概述 为点集生成包含以曼哈顿距离为权的最小生成树所需的“候选边集”，规模至多 4N；再对该边集运行标准 MST 算法得到最终解，整体期望 O(N log N)。

  3. 原文引述

Given N points, returns up to 4*N edges, which are guaranteed to contain a minimum spanning tree for the graph with edge weights w(p, q) = |p.x - q.x| + |p.y - q.y|. Edges are in the form (distance, src, dst). Use a standard MST algorithm on the result to find the final MST. Time: O(N \log N)

  1. 展开阐述

  • 定义与背景

    • 曼哈顿距离 MST：边权 w(p,q)=|px−qx|+|py−qy|。直接在完全图上做 MST 需要 O(N^2 log N) 以上，代价过高。
    • 经典做法：通过坐标变换与扫描结构，仅添加与每点“可能成为最近连接”的少量候选边，保证这些边包含某棵最小生成树。

  • 接口/数据结构（据实现约定）

    • 输入：点集 ps（通常 P=Point 或整型坐标）。
    • 返回：vector{dist, u, v} 三元组，dist 为曼哈顿距离。
    • 后续：在返回的边集上运行 Kruskal 或 Prim 获取最终 MST（Kruskal 配合并查集更常见）。

  • 核心流程/要点（四次变换 + 扫描线/平衡树）

    1. 四象限覆写
      • 循环 k=0..3，分别覆盖曼哈顿距离在四个方向的主导情形。
      • 典型变换模式：
        • 若 k 为奇数：px = -px；否则 swap(px, py)。
      • 变换后，候选“邻居”满足某些有序单调性质，可在一维结构中被捕获。
    2. 排序与次序
      • 对点按自定义比较排序，使得在同一变换下，潜在相连点按“x 主导、y 次之”的顺序出现，便于在线维护。
    3. 扫描结构
      • 维护有序容器 sweep，键一般选取 -py（等价按 py 非增），值为点索引。
      • 扫描到点 i：
        • 从 sweep.lower_bound(-py[i]) 起向后检查“仍可能连边”的候选 j，计算 d = (dx, dy) 在当前变换下的分解。
        • 当 dy > dx 时可提前停止（剪枝）；否则加入边 {dx+dy, i, j}。
        • 最后插入 (-py[i], i)。
    4. 合并结果
      • 四次扫描累计的边总数 ≤ 4N，去重由 Kruskal 在排序阶段自然处理。

  • 复杂度与边界条件

    • 复杂度：每次扫描排序 O(N log N)，容器操作均摊 O(log N)，四次总体 O(N log N)。
    • 边界与退化：
      • 重合点：px、py 完全相同会产生 0 权边，算法可正常处理。
      • 相同坐标轴上大量共线：候选边依然受剪枝控制，规模线性。
      • 整数溢出：dist=|dx|+|dy| 对 32 位整型安全范围较宽，但若坐标绝对值接近上界，建议使用 64 位累加。
    • 精度：实现基于整型，无浮点误差问题；若扩展到浮点坐标，应以 EPS 控制比较与剪枝。

  • 变体/扩展

    • Chebyshev 距离（L∞）MST：可用类似“象限变换+扫描”思想，调整单调条件与剪枝规则。
    • k 近邻稀疏化：在某些场景可用 kd-tree/网格哈希先近邻筛边，再结合本法补全方向性缺失的候选。
    • 与最小生成树协作：候选边生成与 Kruskal 解耦，便于并行化（边生成与排序/并查集可以流水线）。

  • 正确性要点与不变式（直觉）

    • 曼哈顿度量在四个象限的“支配方向”可被线性序捕获；对每点，仅需考虑在该序下不会被其他点“遮挡”的邻居。
    • 四次变换覆盖全部方向情形，保证至少存在一棵 MST 完全由候选边组成。

  • 与相邻技术的对比与取舍

    • 对比“完全图 MST”：由 O(N^2) 边降至 O(N) 级别候选，复杂度显著降低。
    • 与 024-几何-最近点对：最近点对关注全局最短边，而本问题关注连接性与整体最优树；两者可在“候选边筛选”的思路上互借。
    • 与 025-几何-凸包：凸包对极值点选择有类似“方向支配”的思想，但目标问题不同（几何包络 vs 图连通）。
  1. 关联节点

Graph View

Backlinks