1.问题
2.解析
令P为笛卡儿平面上n>1个点构成的集合。简单起见，假设集合中的每个点都不一样。我们还假设这些点是按照其x轴坐标升序排列的。(如果不是这样，可以事先用类似合并排序这样的高效算法对其排序。)为了更加方便，我们还可以按照点的y轴坐标在另一个列表中进行升序排列，并将这个列表示为Q。
当2≤n≤3时，问题就可以通过蛮力算法求解。当n>3时，可以利用点集在x轴方向上的中位数m，在该处作一条垂线，将点集分成大小分别为[n/2]和[n/2]的两个子集P1和Pr。即使得其中[n/2]个点位于线的左边或线上，[n/2]个点位于线的右边或线上。然后就可以通过递归求解子问题P和P来得到最近点对问题的解。其中d1和dr分别表示在P1和Pr中的最近对距离，并定义d = min{d1,dr}。
但请注意，d不一定是所有点对的最小距离，因为距离最近的两个点可能分别位于分界线的两侧。因此，在合并较小子问题的解时，需要检查是否存在这样的点。显然，我们可以只关注以分割带为对称的、宽度为2d的垂直带中的点，因为任何其他点对的距离都至少为d(图5.7(a))。
设S是来自Q，位于分割线2d宽度范围内的垂直带的点的列表。由于Q的特点，因此S是按照y轴坐标升序排列的。我们扫描该列表，当遇到更近的点对时，更新目前为止的最小距离d.min。初始情况下d.min = d，但接下来d.min≤d。设p(x,y)为列表中的点。如果另一个点p(x’,y`)和p点的距离小于d.min，那么在列表S中，p’点一定位于p点后面，并且两点在y轴上的距离一定要小于d.min 。在几何上，这也就意味着p’点一定包含在图5.7(b)的矩形内。该算法的主要原理利用了以下事实:矩形内一般只能够包含少量候选点，因为在矩形每一边(左半边和右半边)内，点与点的距离至少为d。其实很容易证明，在矩形中满足条件的点(包括p在内)的总数不超过8个，更细致的研究表明这个数不会大于6。也就是说，在移动到下一个点之前，算法最多只需要考虑列表S中点p后面的5个点。
3.设计
if n <= 3
返回由蛮力算法求出的最小距离
else
将P的前[n/2]个点复制到P1
将Q的前[n/2]个点复制到Q1
将P中剩下的[n/2]个点复制到Pr
将Q中余下的[n/2]个点复制到Qr
d1<-EfficientClosestPair(P1,Q1)
dr<-EfficientClosestPair(Pr,Qr)
d <- min{d1,dr}
m <- P[[n/2]-1].x
将Q中所有的|x-m|
for i <- 0 to num - 2 do
k<-i+1
while k <= num - 1 and (S[i].y)2 < dminsq
dminsq <-min((S[k].x-S[i].x)_2+(S[k].y-S[i].y)_2,dminsq)
k<-k+1
return sqrt(dminsq)
4.分析
无论将问题划分成两个规模减半的子问题，还是合并子问题的解，该算法都只需要线性时间。因此，假设n是2的幂，我们得到算法运行时间的递归式:
T(n)=2T(n/2)+ f(n)
其中f(n)∈O (n)。应用主定理(其中，a=2，b=2，d=1)，我们得到T(n)∈O(nlogn)。
5.源码
若有收获，就点个赞吧
0 人点赞
