分而治之算法---距离最近的点对.doc

距离最近的点对
给定n 个点(xi,yi)(1≤i≤n),要求找出其中距离最近的两个点。
例14-7 假设在一片金属上钻n 个大小一样的洞,如果洞太近,金属可能会断。若知道任意两个洞的最小距离,可估计金属断裂的概率。这种最小距离问题实际上也就是距离最近的点对问题。
通过检查所有的n(n- 1 ) / 2对点,并计算每一对点的距离,可以找出距离最近的一对点。这种方法所需要的时间为(n2 )。我们称这种方法为直接方法。图1 4 - 1 3中给出了分而治之求解算法的伪代码。该算法对于小的问题采用直接方法求解,而对于大的问题则首先把它划分为两个较小的问题,其中一个问题(称为A)的大小为「n /2ù,另一个问题(称为B)的大小为「n /2ù。初始时,最近的点对可能属于如下三种情形之一: 1) 两点都在A中(即最近的点对落在A中);2) 两点都在B中;3) 一点在A,一点在B。假定根据这三种情况来确定最近点对,则最近点对是所有三种情况中距离最小的一对点。在第一种情况下可对A进行递归求解,而在第二种情况下可对B进行递归求解。
if (n较小) {用直接法寻找最近点对
R e t u r n ; }
// n较大
将点集分成大致相等的两个部分A和B
确定A和B中的最近点对
确定一点在A中、另一点在B中的最近点对
从上面得到的三对点中,找出距离最小的一对点
图14-13 寻找最近的点对
为了确定第三种情况下的最近点对,需要采用一种不同的方法。这种方法取决于点集是如何被划分成A、B的。一个合理的划分方法是从xi(中间值)处划一条垂线,线左边的点属于A,线右边的点属于B。位于垂线上的点可在A和B之间分配,以便满足A、B的大小。
例2-8 考察图14-14a 中从a到n的1 4个点。这些点标绘在图14-14b 中。中点xi = 1,垂线x = 1如图14-14b 中的虚线所示。虚线左边的点(如b, c, h, n, i)属于A,右边的点(如a, e, f, j, k, l) 属于B。d, g, m 落在垂线上,可将其中两个加入A, 另一个加入B,以便A、B中包含相同的点数。假设d ,m加入A,g加入B。
设是i 的最近点对和B的最近点对中距离较小的一对点。若第三种情况下的最近点对比小。则每一个点距垂线的距离必小于,这样,就可以淘汰那些距垂线距离≥的点。图1 4 - 1 5中的虚线是分割线。阴影部分以分割线为中线,宽为2 。边界线及其以外的点均被淘汰掉,只有阴影中的点被保留下来,以便确定是否存在第三类点对(对应于第三种情况)其距离小于。用RA、RB 分别表示A和B中剩下的点。如果存在点对(p,q),p?A, q?B且p, q 的距离小于,则p?RA,q?RB。可以通过每次检查RA 中一个点来寻找这样的点对。假设考察RA 中的p 点,p的y ,那么只需检查RB - <<+ 的q 点,看是否存在与p 间距小于的点。在图14-16a 中给出了包含这种q 点的RB 的范围。因此,只需将RB 中位于×2 阴影内的点逐个与p 配对,以判断p 是否是距离小于的第三类点。这个×2 区域被称为是p paring region)。
例2-9 考察例2 - 8中的1 4个点。A中的最近点对为(b,h),其距离约为0 . 3 1 6。