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

平面点的曼哈顿最小生成树引言作者阅读并研究了由HaiZhou(puterEngineering,NorthwesternUniversity,Evanston,IL60208,USA),NarendraShenoy和WilliamNicholls(AdvancedTechnologyGroup,Synopsys,Inc.,MountainView,CA94043,USA)撰写的论文《EfficientminimumspanningtreeconstructionwithoutDelaunaytriangulation》,现将一些收获体会总结如下。 问题描述平面上有n个不重合的点,你的任务是求这些点的最小生成树。两个点(x0,y0)和(x1,y1)之间的距离定义为|x0-x1|+|y0-y1|。(即曼哈顿距离)如果在任意两个点之间都连一条边,边的权值等于两点的曼哈顿距离,那么这个题目就是标准的最小生成树问题。一个包含n个点n2条边的图,求最小生成树的代价是O(n2)。但是这种一般性的做法没有考虑到“平面”的性质。下面将通过分析最小生成树的性质和平面性质的结合,得到一个O(nlogn)的算法。 最小生成树的“环切”性质先抛开“平面”,我们考虑一般的离散图的最小生成树有什么性质。环切性质在图G=(V,E)中,如果存在一个环,把环中权最大的边e删除得到图G’=(V,E\{e})(如果有多条最大边,则删除任意一条),则G和G’的最小生成树权和相同。证明:假设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,v}中,和u属于同一个集合的点称之为红点,和v属于同一个集合的称之为蓝点。显然S中至少有一个红点(u)、至少有一个蓝点(v)。所以在序列(u,x1,x2,…,xL,v)中必然存在相邻的两个点颜色不同,不妨设为a和b。将<a,b>加入到被删除了e的T中,就得到了一棵新的生成树T’:即T’=(T\{e})∪{<a,b>}。前面提到了通路(u,x1,x2,…,xL,v)中任意一条边都不大于e,所以<a,b>的权不大于e的权。即T’也是G的一棵最小生成树。因为G’是G的子图,所以T’也是G’的最小生成树。而T和T’的权和相等(都是G的最小生成树)。证毕。 区域分类法通过最小生成树的“环切”性质,我们可以发现有很多边是没有用的。如果图中存在一个环,那么就至少能删掉一条边而保持最小生成树不变。我们回到“平面”问题。基本思路还是构建一个离散图——但是这个图的边数必须远远小于n2。换句话说我们要想办法利用“环切”性质,只保留一些有用的边。考察某个点s。我们从s发出8条射线将平面均分成八个部分:如果点落在射线上,按如下方法划分:实线上的点属于这个区域、虚线上的点不属于。上图中p,q都属于该区域。下面我们证明:在每个区域里面,s只要和至多一个点连边即可。八个扇形区域是对称的,我们只考虑R1。把s看作原点,R1里面的点(x,y)都满足:x≥0,y>,不失一