平面点的曼哈顿最小生成树

1、平面点的曼哈顿最小生成树 引言作者阅读并研究了由Hai Zhou (Electrical and ComputerEngineering, Northwestern University, Evanston, IL 60208,USA) , Narendra Shenoy和W illiam Nicholls (AdvancedTechnology Group, Sy nopsys, Inc., Mountain View, CA 94043,USA)撰 写的论文 Efficient minimum spanning tree construction without Delaunay tria

2、ngulation ,现将 一些收获体会总结如下。问题描述平面上有n个不重合的点，你的任务是求这些点的 最小生成树。两个点(x,y。)和(X1,yI)之间的距离定义 为|x0-x1|+|y y|。(即曼哈顿距离)如果在任意两个点之间都连一条边，边的权值等于 两点的曼哈顿距离，那么这个题目就是标准的最小生 成树问题。一个包含n个点n2条边的图，求最小生成 树的代价是O(n2)。但是这种一般性的做法没有考虑到 “平面”的性质。下面将通过分析最小生成树的性质 和平面性质的结合，得到一个O(nlogn)的算法。最小生成树的“环切”性质先抛开“平面”，我们考虑一般的离散图的最小生 成树有什么性质。环切性

3、质 在图 G=(V,E)G=(V,E)中，如果存在一个环，把环 中权最大的边 e e 删除得到图 G G =(V,Ee)=(V,Ee)(如果有 多条最大边，则删除任意一条)，则 G G 和GJ的最小 生成树权和相同。证明：假设e(e E)在G的一个环C上，并且是环上的权最大边。假设G的某棵最小生成树T包含了e,考虑e连接 的两个点u和v。把e从T中删除，就把T分成两个 连通分量，u,v分处不同的连通分量。在环C上对应 的把e删除，从u到v还是有一条通路，并且通路上 的所有边权值都不大于e的权值；假设这条通路是(u, X1, x2, , xL, v)。在点集S=u, X1, X2, , XL,

4、v中，和u属于同 一个集合的点称之为红点， 和v属于同一个集合的称 之为蓝点。显然S中至少有一个红点(u)、至少有一个 蓝点(v)。所以在序列(u, X1, X2, , XL, v)中必然 存在相邻的两个点颜色不同，不妨设为a和b。将入到被删除了e的T中，就得到了一棵新的生成树T ：即T =(T(e) U (。前面提到了通路(u,xi, x2, , xL,v)中任意一条边都不大于e,所以的权不大于e的权。即T也是G的一棵最小生 成树。因为G?是G的子图，所以T也是G的最小生成 树。而T和T的权和相等(都是G的最小生成树)。证毕。区域分类法通过最小生成树的“环切”性质，我们可以发现有 很多边是没

5、有用的。如果图中存在一个环，那么就至 少能删掉一条边而保持最小生成树不变。我们回到“平面”问题。基本思路还是构建一个离散图一一但是这个图的边数必须远远小于n2。换句话说我们要想办法利用“环切”性质，只保留一些有用 的边。考察某个点s。我们从s发出8条射线将平面均分 成八个部分：XX/ RsR4如果点落在射线上，按如下方法划分:p,/I1szz z/F实线上的点属于这个区域、虚线上的点不属于。上 图中p, q都属于该区域。下面我们证明：在每个区域里面，s只要和至多一 个点连边即可。八个扇形区域是对称的，我们只考虑R。把s看作原点，R里面的点(x,y)都满足：x 0,yx.考察R里面两个点p和q,

6、不失一般性设xp xq。1. ypVyq|PQ|=xq+yq-(xp+xq)|SP|=xp+yp|SQ|=Xq+yq所以|PQ|=|SQ|- |SP| yq0X p XqV y qyq时，|PQ|仍然不是三角形SPQ的最长边。(曼哈顿距离意义下的最长)综上，|PQ|无论如何也不可能是三角形SPQ勺最长 边。即：在环中，最大边只可能是|SP|和| SQ|。根据“环切”性质，我们把|SP|和|SQ|中的较长 边删除即可。假设R里面有m个顶点：Pl, P2, , Pm,假设距离s最近的点是R,那么只要在S和R之间连边即可。所谓距离s最近的点，实际上就是xk+yk最小的点。图的构建方法按照上一节介绍的

7、方法，我们可以构建出一个至多 含有8n条边的图。可是如何构造呢？如果对于每个点s,把所有的点都判断一次取最小值，那么复杂度是O(n2),没有任何意义。下面我们考虑设计一个高效的 算法，实现“找到每个点的R区域内，离其最近的点” 的操作。找s的R区域内离s最近的点，实际上就是找s的R区域内x+y最小的点。我们把所有的点按照x从小到大排序：xix2 ,Xk2.y-xyk-xk要满足第一个条件，Q必须属于集合Pk+1, Pk+2, Pn,即Q必然在T中。要满足第二个条件，Q在T中的第一关键字必须大 于yk-xk(定值)。因为我们要使得|PkQ|最小，所以我们实际上就是：从T的第一关键字大于某常数的所

8、有元素中，寻找第 二关键字最小的元素。很明显，T可以用平衡二叉树来实现。按照第一关 键字有序来建立平衡树，对于平衡树每个节点都记录 以其为根的子树中第二关键字最小的是哪个元素。查 询、插入的时间复杂度都是O(logn)。平衡二叉树也可以用线段树代替。对于R,找到符合上述条件并使|PkQ|最小的Q之后, 在Pk和Q之间连一条边，并将R插入T;继续处理Pk-1(除非k=1)。经过上面的处理，我们就把每个点在R区域内的最 近点求出来了。同样的处理R, R3, , R8即可把整 个离散图构建出来。一点优化如果把R, R2, , R8分别处理，则整个算法的复杂度系数过大XX/芯R4我们很容易注意到，R和

9、R是对称的，只要处理其 中一个区域即可。根据对称性，我们只要处理R, R2, R3, R4这四个区域。如果点(x,y)在Ps的R区域内，贝U:1.XXk2.y-xyk-xk如果点(x,y)在Ps的R区域内，贝U:1.xXk2.y-x”和” ”的区别。处理R的时候，任意时刻处理R,我们希望找T中 第一关键字大于某常数的第二关键字最小元素； 处理R的时候，任意时刻处理R,我们要找的就是T中第 一关键字小于某常数的第二关键字最小元素。因而很容易发现,R和R可以和在一起处理。这样我们只要处理R+R、R+R这两种情况即可。时 间复杂度的常系数从8降低到了2。我们按照这样的方法建立的离散图至多含有8n条 边。对该图求最小生成树的时间复杂度为O(