最接近点对问题课件.pptx

《最接近点对问题课件.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章最接近点对问题【问题描述】在应用中，常用诸如点、圆等简单的几何对象来代表现实世界中的实体。在涉及这些几何对象的问题中，常需要了解其邻域中其他几何对象的信息。例如，在空中交通控制问题中，若将飞机作为空间中移动的一个点来看，则具有最大碰撞危险的两架飞机，就是这个空间中最接近的一对点。这类问题是计算几何学中研究的基本问题之一。我们着重考虑平面上的最接近点对问题。最接近点对问题问题提法：给定平面上n个点，找其中的一对点，使得在n个点所组成的所有点对中，该点对间的距离最小。说明：严格来讲，最接近点对可能多于一对，为简便起见，我们只找其中的一对作为问题的解。一

2、个简单的做法是将每一个点与其他n-1个点的距离算出，找出最小距离的点对即可。该方法的时间复杂性是T(n)=n(n-1)/2+n=O(n2)，效率较低。已经证明，该算法的计算时间下界是Ω(nlogn)。蛮力算法算法BruteForceClosestPoints(P)//输入:一个n(n≥2)个点的列表P,P1=(x1,y1)….,Pn=(xn,yn)//输出:两个最近点的下标,index1和index2dmin=∞fori=1ton-1doforj=i+1tondod=sqrt((xi-xj)2+(yi-yj)2)ifd

3、=i;index2=jreturnindex1,index2总结:此算法的时间复杂度是O(n2)计算距离：n(n-1)/2次If语句最多执行n次n(n-1)/2+n算法的应用最接近点对问题常用于空中交通的计算机自动控制系统中，也是计算机几何学研究的基本问题之一。假设在一片金属上钻n个大小一样的洞，如果洞太近，金属可能会断。若知道任意两个洞的最小距离，可估计金属断裂的概率。这种最小距离问题实际上也就是距离最近的点对问题。一维空间找最接近点对怎么样在一条线上找最邻近的点对?(1)用O(nlogn)时间对它们排序.(2)走过排好序的表,计算每一个点到跟在它后面

4、的点的距离,容易看出这些距离的最小值.时间复杂性为：n-1故T(n)=O(nlogn)+(n-1)=O(nlogn)显然，这种方法不能推广到二维的情形。故尝试用分治法来求解，并希望推广到二维的情形。分治策略下一维的情形先把x1,x2,…,xn排好序，再进行一次线性扫描就可以找出最接近点对，T(n)=O(nlogn)。假设我们用x轴上某个点m将S划分为2个子集S1和S2，基于平衡子问题的思想，用S中各点坐标的中位数来作分割点。递归地在S1和S2上找出其最接近点对{p1,p2}和{q1,q2}，并设d=min{

5、p1-p2

6、,

7、q1-q2

8、}，S中的最接近点

9、对或者是{p1,p2}，或者是{q1,q2}，或者是某个{p3,q3}，其中p3∈S1且q3∈S2。原问题不太好解决，可以把原问题分解为若干个规模较小的相同子问题，再把子问题的解合并为原问题的解大致算法：1、用S中各点坐标的中位数来作分割点，将S分成S1和S2。2、递归地在S1和S2上找出其最接近点对{p1,p2}和{q1,q2}。3、合并：S中的最接近点对在{p1,p2}、{q1,q2}、{p3,q3}中，p3∈S1且q3∈S2。如果S的最接近点对是{p3,q3}，即

10、p3-q3

11、

12、即p3∈(m-d,m]，q3∈(m,m+d]。由于在S1中，每个长度为d的半闭区间至多包含一个点（否则必有两点距离小于d），并且m是S1和S2的分割点，因此(m-d,m]中至多包含S中的一个点。由图可以看出，如果(m-d,m]中有S中的点，则此点就是S1中最大点。同理，如果(m,m+d]中有S中的点，则此点就是S2中最小点。因此，我们用线性时间就能找到区间(m-d,m]和(m,m+d]中所有点，即p3和q3。从而我们用线性时间就可以将S1的解和S2的解合并成为S的解。publicstaticdoubleCpair1(S,d)//找S中最接近点对的距离d{

13、n=

14、S

15、;//S中点的个数if(n<2)d=∞；m=S中各点坐标的中位数;构造S1和S2;//S1={x∈S

16、x<=m},S2={x∈S

17、x>m}Cpair1(S1,d1);Cpair1(S2,d2);p=max(S1);q=min(S2);d=min(d1,d2,q-p);returntrue;}O(n)2T(n/2)O(n)T(n)=O(nlogn)最接近点对问题下面来考虑二维的情形。选取一垂直线l:x=m来作为分割直线。其中m为S中各点x坐标的中位数。由此将S分割为S1和S2。递归地在S1和S2上找出其最小距离d1和d2，并设d=min{d1,d

18、2}，S中的最接近点对或者是d，或者是某个{p,q}，其中p∈S1且q∈S2。能