曼哈顿距离最小生成树
问题
给你平面上的
朴素算法
由于完全图的边数是
平面划分
鉴于完全图边数十分之多,然而生成树上的边却只有
事实上确实如此,如果我们随意选择一个点作为中心
上图中
接下来我们将证明,对于每一个区域,只需要留下离
假设现在在区域
设
情况2:
此时有:
情况2:
此时有:
如果
由于在区域
情况3:
此时有:
由于
所以
情况4:
这种情况违反了
综上,在区域
对于其它的区域,都可以通过对称或者旋转,从而变成
这样一来,每个点只用连出
一条边在上面的图中被两个端点都被计数了一次,所以最终的边数是不超过
求出最近点
上面的性质中还留下一个问题:如何求出每个区域内离
从之前的关于边数的讨论中可知,我们只用求
考虑使用扫描线算法:将所有点按照
这个算法是
至于坐标变换,一个比较方便的顺序就是先关于
-
对于图上一个环,删去环上权重最大的边后的图的最小生成树与原图一致。证明在很多地方都有。 ↩