4-finding the closet pair of points

《4-finding the closet pair of points》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、分治法例：寻找最近点对（FindingtheClosetPairofPoints）问题：给定平面上的n个点，要找出距离最近的两个点。Brute-force法：把Cn2个点对的距离逐一计算一遍，在计算过程中纪录下：到目前为止距离最近的点对。这样，当所有的点对都被检查过之后，答案也就得到了。但算法的时间复杂度为Q(n2),∵点对共有Cn2=n(n-1)/2个。能否使用分治法？如何使用分治法？找一条垂直线把平面分成两部分，使得线左边和线右边的点的数目基本相等。怎样才能快速进行分割？若我们事先用O(nlogn)

2、时间对x坐标进行排序，使得所有的点是按x坐标从小到大排好序的（x坐标相同时y坐标小的排前），那么我们只要取下标小的én/2ù个点属于左边的点集PL，取下标大的ën/2û个点属于右边的点集PR，即用O(1)时间就可以将规模为n的问题分解为两个规模为n/2的、同类型的子问题。分割完毕之后就可以采用分治法，分别求出PL和PR中的最近点对。但是需要注意的是，整个点集中的最近点对不一定是上面求出的两个最近点对中的一个，而有可能是这样的点对：其中的一个点在PL中而另一个点PR在中。显然，我们不能对具有性质uÎPL且

3、vÎPR的所有点对(u,v)进行逐一的检查，否则仅此一项检查就需要Q(n2)时间（共有n2/4个点对），因为此时的PL和PR中各有约n/2的点。记dL是左边的点集PL中的最近点对的距离，dR是右边的点集PR中的最近点对的距离，则整个点集合中的最近点对距离不会大于d=min{dL,dR}。因此，如果我们找好分割线，我们就只需要考虑落入到以分割线为中心、到两侧的距离各为d的带状区域内的点。但是，全部点都落到带状区域内的可能性也存在。所以，对带状区域内的点的检查次数还需要压缩。分析：若最近点对的两个点分属于P

4、L和PR，则两点之间的y坐标值之差必定小于d（直角三角形的任一直角边必定小于斜边）。因此，如果p是最近点对中y坐标值较小的一个点，则另一个点q必然落在如图所示的d´2d矩形之中。d´2d矩形之外的任何点不可能与p点一起构成最近点对。可以证明，当d=min{dL,dR}时，在d´2d矩形之内，最多有4个点属于PL；同理也最多有4个点属于PR。（证明留作作业）因此，如果落入带状区域内的所有的点均已按y坐标从小到大的次序排好，那么，对其中任何一个点p，我们最多只要依次检查排在p后面的7个点。实际执行时，检查次

5、数还可能少于7次：只要当前被检查的点的y坐标值与p点的y坐标值之差大于等于d，我们就可以立即停止对p点的检查，（因为该点以及排在该点之后的点，已无可能与p点一起构成最近点对。）也就是说，我们能够在常数时间里完成对任何一个点p的检查。所以，若我们当前的处理对象有m个点，即使在最坏情况下，亦即全部m个点均落入带状区域内时，对这m个点的检查也只需要Q(m)时间。设求解规模为m的最近点对问题的时间复杂度为T(m)。当我们如前面所述的那样，把一个规模为m的问题分为两个规模为m/2的同类型子问题时，则两个子问题的求

6、解时间共为2T(m/2)。如果我们能够保证在其余工作上所花的时间也不超过Q(m)的话，那么我们就可有T(m)=2T(m/2)+Q(m)=Q(mlogm)。于是当m取为n时，就有T(n)=Q(nlogn)，这当然比Brute-force法要好许多。前面已经讲到，对落入带状区域内的点的检查不超过O(m)时间需要有一个前提，那就是落入带状区域内的点要已经按照y坐标从小到大的次序排好。如果在分治过程中每次都要对所涉及点的y坐标进行彻底的排序，那么就不可能在O(m)时间里完成对m个数据元素的排序。但是，如果提供给

7、我们的m个点的y坐标是已经排好序的（初始时我们可以进行一次预处理，用Q(nlogn)时间对y坐标进行排序），那么我们就可以利用数据之间的关系，在不超过O(m)的时间里，把m个y坐标分拆为左、右两个部分（每部分分别有ém/2ù个和ëm/2û个y坐标）、且使得这两部分的y坐标也是排好序的；同样也能在不超过O(m)的时间里，使得落入带状区域内的点按y坐标排好序。另外，由于分治是按x坐标进行的，为了便于分治，如前面介绍的那样，在初始时我们对x坐标也要进行一次预处理，即用Q(nlogn)时间对其进行排序。所有点的

8、x坐标一旦排好之后就不允许再改变其相互位置。这样在分治时，只要根据存放x坐标的X数组的下标，就可以用O(1)时间把m个点的集合分为两个各有m/2个点的子集合。e.g.如要对x坐标在X[j]到X[k]这一段中的m个点（j