Rectilinear MST

平面完全图边权为曼哈顿距离;算法一用 8 个八分圆候选边 + Kruskal,算法二用四象限 Borůvka。

标签 生成树 / 曼哈顿距离 / 计算几何 / Borůvka

题目描述

给定平面上的 𝑛 个点 (𝑥𝑖,𝑦𝑖)。在完全图上定义边权

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

求该图最小生成树的权值和。

1≤𝑛≤105,|𝑥𝑖|,|𝑦𝑖|≤109。

题解

算法一:Kruskal

完全图有 𝑂(𝑛2) 条边,不能显式建图。对每个点,只需要保留它在 8 个八分圆内最近的邻居。

以点 𝑝 为原点,四条直线

𝑥=𝑥𝑝,𝑦=𝑦𝑝,𝑥−𝑦=𝑥𝑝−𝑦𝑝,𝑥+𝑦=𝑥𝑝+𝑦𝑝

把平面分成 8 个 45° 区域。在每个区域内,曼哈顿距离去掉绝对值后是一个线性函数。例如点 𝑞 在 𝑝 的东北偏东区域时,𝑥𝑞≥𝑥𝑝、𝑦𝑞≥𝑦𝑝 且 𝑥𝑞−𝑥𝑝≥𝑦𝑞−𝑦𝑝,距离化为

𝑑(𝑝,𝑞)=(𝑥𝑞+𝑦𝑞)−(𝑥𝑝+𝑦𝑝)

因此找最近点只需要在区域内最小化 𝑥𝑞+𝑦𝑞。

关键是 45° 这个宽度:若 𝑢,𝑣 在 𝑝 的同一个八分圆内,且 𝑑(𝑝,𝑢)≤𝑑(𝑝,𝑣),则 𝑑(𝑢,𝑣)≤𝑑(𝑝,𝑣)。所以任何非最近边都可以被替换,MST 只需要每个八分圆内的最近邻候选。

理论上每个点只需保留 8 条候选边,候选图有 𝑂(𝑛) 条边;用扫描线生成一组同样充分的 𝑂(𝑛) 条候选边,再跑 Kruskal。

求每个八分圆的最近邻时,利用对称性只做 4 次坐标变换;每次按 𝑥+𝑦 排序,用扫描线维护 𝑦 方向的最优候选。总复杂度 𝑂(𝑛log𝑛)。

算法二:Borůvka

算法一先一次性生成 𝑂(𝑛) 条候选边,再跑 Kruskal。也可以直接在隐式完全图上跑 Borůvka,每轮为每个连通块找最小出边。

对每个点 𝑝,把平面按两条坐标轴分成四个象限。每轮对每个点查询:在每个象限内,找与 𝑝 不在同一连通块的曼哈顿最近点。对每个连通块,取块内所有点级候选的最小者,作为该块的最优出边。

正确性:设 𝑒=(𝑝,𝑣) 是连通块 𝐶 的最小出边。对任意 𝑢∉𝐶,都有 𝑑(𝑝,𝑢)≥𝑑(𝑝,𝑣),否则 (𝑝,𝑢) 会是更小的出边。因此 𝑣 已经是 𝑝 到块外所有点的最近点,当然也是 𝑣 所在象限内的最近块外点。所以四象限查询一定找到 𝑒 或与它等权的边。这里四个象限就够;8 个八分圆是算法一构造静态候选图时需要的更强条件。

每个象限内距离仍可线性化。例如东北象限 𝑥𝑞≥𝑥𝑝、𝑦𝑞≥𝑦𝑝 中,

𝑑(𝑝,𝑞)=(𝑥𝑞+𝑦𝑞)−(𝑥𝑝+𝑦𝑝)

最近点就是最小化 𝑥𝑞+𝑦𝑞。其余象限用坐标翻转复用同一套扫描。

每轮对四个象限分别扫描:先把该象限翻转到东北方向,按 𝑥 从大到小处理,用树状数组 / 线段树维护 𝑦 后缀上的最优候选。每个结构节点维护来自不同分量的前两名,查询时跳过当前分量。每轮 𝑂(𝑛log𝑛),Borůvka 最多 𝑂(log𝑛) 轮,总复杂度 𝑂(𝑛log2𝑛)。

坐标轴上的点要固定归入相邻象限之一,或两边都放;重合点距离为 0,最好先合并或单独处理。

复杂度

算法一为 𝑂(𝑛log𝑛);算法二每轮 𝑂(𝑛log𝑛),Borůvka 共 𝑂(log𝑛) 轮,总复杂度 𝑂(𝑛log2𝑛),空间 𝑂(𝑛)。

源码位置