二维空间求近点对算法模板.doc

《二维空间求近点对算法模板.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、二维空间求最近点对算法模板（分治法）选取一垂直线l:x=m来作为分割直线。其中m为S中各点x坐标的中位数。由此将S分割为S1和S2。递归地在S1和S2上找出其最小距离d1和d2，并设d=min{d1,d2}，S中的最接近点对或者是d，或者是某个{p,q}，其中p∈P1且q∈P2，如图所示。                                      能否在线性时间内找到p,q？考虑P1中任意一点p，它若与P2中的点q构成最接近点对的候选者，则必有distance(p，q)＜d。满足这个条件的P2中的点一定落在一个d×2d的矩形R中，如图所示

2、。由d的意义可知，P2中任何2个S中的点的距离都不小于d。由此可以推出矩形R中最多只有6个S中的点。                           证明：将矩形R的长为2d的边3等分，将它的长为d的边2等分，由此导出6个(d/2)×(2d/3)的矩形（如图(a)所示）。若矩形R中有多于6个S中的点，则由鸽舍原理易知至少有一个(d/2)×(2d/3)的小矩形中有2个以上S中的点。设u，v是位于同一小矩形中的2个点，则                         因此，distance(u,v)

3、S中的点。极端情形：图(b)是矩形R中恰有6个S中的点的极端情形。                     因此，在分治法的合并步骤中最多只需要检查6×n/2=3n个候选者。为了确切地知道要检查哪6个点，可以将p和P2中所有S2的点投影到垂直线l上。由于能与p点一起构成最接近点对候选者的S2中点一定在矩形R中，所以它们在直线l上的投影点距p在l上投影点的距离小于d。由上面的分析可知，这种投影点最多只有6个。因此，若将P1和P2中所有S中点按其y坐标排好序，则对P1中所有点，对排好序的点列作一次扫描，就可以找出所有最接近点对的候选者。对P1中每一点最多只要

4、检查P2中排好序的相继6个点。算法描述：publicstaticdoubleCPair2(S){n=

5、S

6、;if(n<;¥2)returnm=S中各点x间坐标的中位数;构造S1和S2；//S1={p∈S

7、x(p)<=m}, S2={p∈S

8、x(p)>m}d1=cpair2(S1);d2=cpair2(S2);dm=min(d1,d2);设P1是S1中距垂直分割线l的距离在dm之内的所有点组成的集合；模板程序：#include#include#includeusingnamespacestd;#def

9、ineMAXN100000structnode{doublex,y;}point[MAXN];//存放点的结构体数组boolcal_less(nodep1,nodep2){if(p1.x!=p2.x)returnp1.x

10、){if(l==r)return1000000000;if(l==r-1)returndist(point[l],point[r]);if(l==r-2)returngetmin(getmin(dist(point[l],point[l+1]),dist(point[l+1],point[l+2])),dist(point[l],point[l+2]));inti,j,mid=(l+r)>>1;doublecurmin=getmin(solve(l,mid),solve(mid+1,r));for(i=l;i<=r;i++)for(j=i+1;j<=i+

11、5&&j<=r;j++){curmin=getmin(curmin,dist(point[i],point[j]));}returncurmin;}//入口函数，n代表点的个数doubleClosestPairDistance(intn){sort(point,point+n,cal_less);returnsolve(0,n-1);}