1、将所给的平面上n个点的集合S分成两个子集S1和S2 ，每个子集中约有n/2个点 。然后在每个子集中递归地求其最接近的点对。在这里，一个关键的问题是如何实现递归法中的合并步骤，即由S1 和S2的最接近点对，如何求得原集合S中的最接近点对。如果组成S的最接近点对的两个点都在S1中或都在S2中，则问题很明显就可以找到答案。可是还存在另外一种可能，就是这两给点分别在S1和S2 中的时候。下面主要讨论这种情况。2.1 一维情形下的分析为使问题易于理解和分析，我们先来考虑一维的情形。此时，S中的n各点退化为x轴上的n个实数x1，x2，x3xn。最接近点对即为这n个实数中相差最小的两个实数。我们尝试用递归法
2、来求解，并希望推广到二维的情形。假设我们用x轴上的某个点m将S划分为两个集合S1和S2 ，使得S1=xS | xm ;S2 = xS | xm 。这样一来，对于所有p和qS2 有pq。 递归地在S1和S2 上找出其最接近点对p1，p2和q1，q2，并设d=min| p1- p2|，| q1- q2|由此易知，S中的最接近进点对或者是 p1 ，p2，或者是 q1 ，q2，或者是某个p3，q3，其中，p3S1且q3S2 。如图2-1-1所示。 图2-1-1 一维情形的递归法 我们注意到，如果S的最接近点对是p3，q3，即|p3-q3|d，则p3和q3两者与m的距离不超过d，即| p3-m|d，|
3、q3 -m|d。也就是说 ，p3（m-d，m，q3（m，m+d。由于每个长度为d的半闭区间至多包含S1中的一个点，并且m是S1和S2 的分割点，由图2-1-1可以看出，如果（m-d，m中有S中点 ，则此点就是S1中最大点。同理，如果（m，m+d中有S中点，则此点就是S2 中最小点。因此，我们用线性时间就能找到区间（m-d，m和（m，m+d中所有点，即p3和q3。从而我们用线性时间就可以将S1的解和S2 的解合并成为S的解。但是，还有一个问题需要认真考虑，即分割点m的选取，即S1和S2 的划分。选取分割点m的一个基本要求是由此将S进行分割，使得S= S1S2 ，S1，S2 ，且S1x|xm ,S
4、2 x| xm 。容易看出，如果选取m=max（S）+min（S）/2，可以满足分割要求。然而，这样选取分割点，有可能造成划分出的子集S1和S2 的不平衡 。例如在最坏情况下，| S1|=1，| S2 |=n-1，这样的计算效率与分割前相比提高幅度不明显。这种现象可以通过递归法中“平衡子问题”的方法加以解决。我们可以适当选择分割点m，使S1和S2 中有个数大致相等的点。我们会想到用S中各点坐标的中位数来作为分割点。 由此，我们设计出一个求一维点集S的最接近点对的算法Cpair 1如下：-Bool Cpair 1（S,d）N=|S|;if（n2） d=; return false;m=S中各点坐
5、标的中位数；/构造S1和S2 ； S1=xS | xm ;S2 = xS | xm ;Cpair 1（S1,d1）;Cpair 1（S2 ,d2）;p=max（S1）;q=min（S2 ）;d=min（d1,d2,q-p）;return true-2.2 二维情形下的分析 以上一维算法可以推广到二维的情形。 设S中的点为平面上的点，它们都有两个坐标值x和y。为了将平面上点集S线性分割为大小大致相等的两个子集S1和S2 ，我们选取一垂直线L：x=m来作为分割直线。其中，m为S中各点x坐标的中位数。由此将S分割为S1=pS | x （p） m 和S2 =pS | x （p） m 。从而使S1和S2
6、 分别位于直线L的左侧和右侧，且S=S1S2 。由于m是S中各x坐标的中位数，因此S1和S2 中得点数大致相等。 递归地在S1和S2 上解最接近点对问题，我们分别得到S1和S2 中的最小距离d1和d2。现设d=mind1,d2。若S的最接近点对（p,q）之间的距离小于d，则p和q必分属于S1和S2 。不妨设pS1，qS2 。那么p和q距直线L的距离均小于d。因此，若我们用P1和P2分别表示直线L的左边和右边的宽为d的两个垂直长条区域，则pP1且qP2，如图2-2-1所示。图2-2-1 距直线L的距离小于d的所有点在一维情形下 ，距分割点距离为d的两个区间（m-d，m和（m，m+d中最多各有S中
7、一个点。因而这两点成为唯一的未检查过的最接近点对候选者。二维的情形则要复杂些。此时，P1中所有点和P2中所有点构成的点对均为最接近点对的候选者。在最坏的情况下有n2/4对这样的候选者。考虑P1中任意一点p，它若与P2中的点q构成最接近点对的候选者，则必有distance（p,q） d。满足这个条件的P2中的点有多少个呢？容易看出这样的点一定落在一个d*2d的矩形R中，如图2-2-2所示。图2-2-2 包含点q的d*2d矩形R由d的意义可知，P2中任何两个S中的点的距离都不小于d。由此可以推出矩形R中最多只有6个S中的点。下面我们来证明这个结论 。我们可以将矩形R的长为2d的边3等分，将它的长为
8、d的边2等分，由此导出6个（d/2）*（2d/3）的矩形。如图2-2-3（a） 所示。 如图2-2-3 矩形R中点的稀疏性 若矩形R中有多于6个S中的点，则由鸽舍原理易知至少有一个（d/2）*（2d/3）的小矩形中有2个以上S中的点。设u，v是这样2个点，它们位于同一小矩形中，则（x（u）-x（v）2+（y（u）-y（v）2 （d/2）2+（2d/3）2=25/36d2 因此， distance（u,v） 5d/6d。这与d的意义相矛盾。也就是说矩形R中最多只有6个S中的点。图2-2-3（b）是矩形中恰有6个S中点的极端情形。由于这种稀疏性质 ，对于P1中任意一点p，P2中最多只有6个点与它构
9、成最接近点对的候选者。因此，在递归法的合并步骤中，我们最多只需要检查6*n/2=3n个候选者，而不是n2/4个候选者。我们将p和P2中所有S2 的点投影到垂直线L上。由于能与p点一起构成最接近点对候选者的S2 中点一定在矩形R中，所以它们在直线L上的投影点距p在L上投影点的距离小于d。由上面的分析可知， 这种投影点最多只有6个。因此，若将P1和P2中所有S中点按其y坐标排好序，则对P1中所有点，对排好序的点列做一次扫描，就可以找出所有最接近点对的候选者。对P1中每一点最多只要检查P2中排好序的相继6个点。至此，我们给出用递归法求二维点集最接近点对的算法Cpair 2 如下：-bool Cpai
10、r 2（S,d）If（n2）d=;Return false;1. m=S中各点x间坐标的中位数；构造S1和S2 ；/S1=pS| x（p）m 2. Cpair 2（S1,d1）;Cpair 2（S2 ,d2）;3. dm=min（d1,d2）;4. 设P1是S1中距垂直分割线L的距离在dm之内的所有点组成的集合；P2是S2 中距分割线L的距离在dm之内所有点组成的集合；将P1和P2中点依其y坐标值排序；并设X和Y是相应的已经排好序的点列；5. 通过扫描X以及对于X中每个点检查Y中与其距离在dm内的所有点（最多6个）可以完成合并；当X中的扫描指针逐次向上移动时，Y中的扫描指针可在宽为2dm的一个
11、区间内移动；设dl是按这种扫描方式找到的点对间的最小距离；6. d=min（dm，dl）；return true；-2.3 算法优化在以上二维情形下的算法中，在每次执行第4步时都要进行排序，这将花费较多的时间，从而增加算法的复杂度。因此，在这里我们要作一个技术处理。我们采用设计算法时常用的预排序技术，在使用递归法之前，预先将S中n个点依其y坐标值排好序，设排好序的点列为P*。在执行递归法的第4步时，只要对P*作一次线性扫描，即可抽取出我们所需要的排好序的点列X和Y。然后，在第5步时再对X作一次线性扫描，即可求得dl。2.4 算法实现 在具体实现算法Cpair 2时，我们分别用类Point X和
12、Point Y表示依x坐标和依y坐标排序的点。-Class Point X Public: Int operator=（Point X a） constreturn （x=a.x）; Private: Int ID; /点编号 Float x,y; /点坐标;Class Point YPublic: int operator=（Point Y a） constreturn （y=a.y）Private: Int p; /同一点在数组X中的坐标 Float x,y;；-平面上任意两点u和v之间的距离可计算如下：-Template Inline float distance（const Type
13、& u,const Type & v）Float dx=u.x-v.x;Float dy=u.y-v.y;Return sqrt（dx * dx + dy * dy）; 在算法Cpair 2中，用数组X存储输入的点集。在算法的预处理阶段，将数组X中的点依x坐标和依y坐标排序，排好序的点集分别存储在数组X和数组Y中。事实上，我们只要取m=（L+r）/2，则XL:m和Xm+1:r就是满足要求的分割。依y坐标排好序的数组Y用于在算法的合并步中快速检查d矩形条内最接近点对的候选者。-Bool Cpair 2（Point X X,int n,Point X&a,Point X&b,float&d） If
14、（n2） return false; MergeSort（X,n）; Point Y * Y =new Point Y n; For （int i = 0; i n ; i+） /将数组X中的点复制到数组Y中 Yi.p = i ; Yi.x =Xi.x ; Yi.y =Xi.y ; MergeSort （Y,n）;Point Y * Z = new Point Y n;Closest （X,Y,Z,0,n-1,a,b,d）;delete Y;delete Z;return true;算法Cpair 2中，具体计算最接近点对的工作由函数closest完成。Viod closest （Point
15、X X, Point Y Y, Point Y Z,int L,int r,Point X& If （r 1 = = 1） /2点的情形 a = XL; b =Xr; d =distance（XL,Xr）; return; If（r 1 = = 2） /3点的情形 Float d1 = distance （XL,XL+1）; Folat d2 = distance （XL+1,Xr）; Float d3 = distance （XL,Xr）; If （dL= d2 & dL=d3） a = XL; b =XL+1; d =dL; return; If （d2 a = XL+1; b = Xr;
16、 d = Xd2; else b =Xr; d =d3; /多于3点的情形，用递归法Int m = （L+r）/2;Int f = L, g = m + 1;For （ int i = 1;im） Zg+ = Yi; Else Zf+ = Yi ;Closest （X,Z,Y,L,m,a,b,d）;Float dr;Point X ar ,br;Closest （X,Y,Z,m+L,r,ar,br,dr）;If （drd） a = ar;b = br;d =dr;Merge（Z,Y,L,m,r）; /重构数组 Y /d矩形条内的点置于Z中Int k = L;For （int i = L, i=
17、 r, i+） If（fabs（Ym.x Yi.x） Zk+=Yi; /搜索ZL:k-1 For（int i = L;=k;i+） For （int j =i+1;jk & Zj.y Zi.y d; j+） Float dp = distance （Zi,Zj）; If （dp p） d = dp; a =XZi.p; b =XZj.p; 3、结论3.1.对于一类问题，如果该问题规模为n，但是可以分解为k个互相独立且与原问题相同的规模较小的子问题的话，我们就可以运用递归法，递归的解决这些子问题，然后将各子问题的解合并得到原问题的解。 3.2 通过对最接近点对问题的解决 ，熟悉了解决问题的基本步骤和方法：首先对问题进行分类，然后运用该类问题的处理思路进行算法的设计，最后还要考察所设计算法的复杂性，进一步进行优化处理。
