Rectilinear MST
平面完全图边权为曼哈顿距离;算法一用 8 个八分圆候选边 + Kruskal,算法二用四象限 Borůvka。标签 生成树 / 曼哈顿距离 / 计算几何 / Borůvka
题目描述
给定平面上的 个点 。在完全图上定义边权
求该图最小生成树的权值和。
,。
题解
算法一:Kruskal
完全图有 条边,不能显式建图。对每个点,只需要保留它在 8 个八分圆内最近的邻居。
以点 为原点,四条直线
把平面分成 8 个 45° 区域。在每个区域内,曼哈顿距离去掉绝对值后是一个线性函数。例如点 在 的东北偏东区域时,、 且 ,距离化为
因此找最近点只需要在区域内最小化 。
关键是 45° 这个宽度:若 在 的同一个八分圆内,且 ,则 。所以任何非最近边都可以被替换,MST 只需要每个八分圆内的最近邻候选。
理论上每个点只需保留 8 条候选边,候选图有 条边;用扫描线生成一组同样充分的 条候选边,再跑 Kruskal。
求每个八分圆的最近邻时,利用对称性只做 4 次坐标变换;每次按 排序,用扫描线维护 方向的最优候选。总复杂度 。
算法二:Borůvka
算法一先一次性生成 条候选边,再跑 Kruskal。也可以直接在隐式完全图上跑 Borůvka,每轮为每个连通块找最小出边。
对每个点 ,把平面按两条坐标轴分成四个象限。每轮对每个点查询:在每个象限内,找与 不在同一连通块的曼哈顿最近点。对每个连通块,取块内所有点级候选的最小者,作为该块的最优出边。
正确性:设 是连通块 的最小出边。对任意 ,都有 ,否则 会是更小的出边。因此 已经是 到块外所有点的最近点,当然也是 所在象限内的最近块外点。所以四象限查询一定找到 或与它等权的边。这里四个象限就够;8 个八分圆是算法一构造静态候选图时需要的更强条件。
每个象限内距离仍可线性化。例如东北象限 、 中,
最近点就是最小化 。其余象限用坐标翻转复用同一套扫描。
每轮对四个象限分别扫描:先把该象限翻转到东北方向,按 从大到小处理,用树状数组 / 线段树维护 后缀上的最优候选。每个结构节点维护来自不同分量的前两名,查询时跳过当前分量。每轮 ,Borůvka 最多 轮,总复杂度 。
坐标轴上的点要固定归入相邻象限之一,或两边都放;重合点距离为 0,最好先合并或单独处理。
复杂度
算法一为 ;算法二每轮 ,Borůvka 共 轮,总复杂度 ,空间 。