《最接近点对问题课件资料》由会员分享，可在线阅读，更多相关《最接近点对问题课件资料（27页珍藏版）》请在金锄头文库上搜索。
1、第2章 最接近点对问题 【问题描述】 在应用中，常用诸如点、圆等简单的几何对 象来代表现实世界中的实体。在涉及这些几何对象 的问题中，常需要了解其邻域中其他几何对象的信 息。 例如，在空中交通控制问题中，若将飞机作 为空间中移动的一个点来看，则具有最大碰撞危险 的两架飞机，就是这个空间中最接近的一对点。 这类问题是计算几何学中研究的基本问题之 一。我们着重考虑平面上的最接近点对问题。 最接近点对问题 v问题提法：给定平面上n个点，找其中的一对点， 使得在n个点所组成的所有点对中，该点对间的距 离最小。 v说明： 严格来讲，最接近点对可能多于一对，为简便起见，我 们只找其中的一对作为问题的解。
2、一个简单的做法是将每一个点与其他n-1个点的距离算出 ，找出最小距离的点对即可。该方法的时间复杂性是 T(n)=n(n-1)/2+n=O(n2)，效率较低。 已经证明，该算法的计算时间下界是(nlogn)。 蛮力算法 v算法 BruteForceClosestPoints(P) v/输入:一个n(n2)个点的列表P,P1=(x1,y1).,Pn=(xn,yn) v/输出:两个最近点的下标,index1和index2 vdmin= vfor i= 1 to n-1 do v for j= i+1 to n do v d=sqrt(xi-xj)2+(yi-yj)2) v if ddmin v dm
3、in=d ; index1=i ; index2=j vreturn index1,index2 总结:此算法的时间复杂度是O(n2) 计算距离：n(n-1)/2次 If 语句最多执行n次 n(n-1)/2+n 算法的应用 v最接近点对问题常用于空中交通的计算机自动控 制系统中，也是计算机几何学研究的基本问题之 一。 v假设在一片金属上钻n 个大小一样的洞，如果洞 太近，金属可能会断。若知道任意两个洞的最小 距离，可估计金属断裂的概率。这种最小距离问 题实际上也就是距离最近的点对问题。 一维空间找最接近点对 v怎么样在一条线上找最邻近的点对? v(1)用O(nlogn)时间对它们排序. v(2
4、)走过排好序的表,计算每一个点到跟在它后面的 点的距离,容易看出这些距离的最小值.时间复杂性 为：n-1 故T (n)= O(nlogn)+(n-1)= O(nlogn) 显然，这种方法不能推广到二维的情形。 故尝试用分治法来求解，并希望推广到二维的情 形。 分治策略下一维的情形 v先把x1,x2,xn排好序，再进行一次线性扫描就可以找出最 接近点对，T(n)=O(nlogn)。 v假设我们用x轴上某个点m将S划分为2个子集S1和S2 ，基于 平衡子问题的思想，用S中各点坐标的中位数来作分割点。 v递归地在S1和S2上找出其最接近点对p1,p2和q1,q2，并设 d=min|p1-p2|,|q
5、1-q2|，S中的最接近点对或者是p1,p2 ，或者是q1,q2，或者是某个p3,q3，其中p3S1且 q3S2。 原问题不太好解决，可以把原问题分解为若干个规 模较小的相同子问题，再把子问题的解合并为原问 题的解 大致算法： 1、用S中各点坐标的中位数来作分割点，将S分成S1和S2 。 2、递归地在S1和S2上找出其最接近点对p1,p2和q1,q2。 3、合并： S中的最接近点对在 p1,p2、q1,q2、p3,q3 中 ， p3S1且q3S2。 u如果S的最接近点对是p3,q3，即|p3-q3|d，则p3和q3两 者与m的距离不超过d，即p3-md，q3-md,即p3(m-d,m ，q3(
6、m,m+d 。 u由于在S1中，每个长度为d的半闭区间至多包含一个点（否则 必有两点距离小于d），并且m是S1和S2的分割点，因此(m- d,m中至多包含S中的一个点。由图可以看出，如果(m-d,m中 有S中的点，则此点就是S1中最大点。同理，如果(m,m+d中有 S中的点，则此点就是S2中最小点。 u因此，我们用线性时间就能找到区间(m-d,m和(m,m+d中所 有点，即p3和q3。从而我们用线性时间就可以将S1的解和S2的 解合并成为S的解。 vpublic static double Cpair1(S,d) /找S中最接近点对的距离d v v n=|S|; /S中点的个数 v if(n2
7、) v d=； v m=S中各点坐标的中位数; v 构造S1和S2; v /S1=xS|xm v Cpair1(S1,d1); v Cpair1(S2,d2); v p=max(S1); v q=min(S2); v d=min(d1,d2,q-p); v return true; v O(n) 2T(n/2) O(n) T(n)=O(nlogn) 最接近点对问题最接近点对问题 u下面来考虑二维的情形。 选取一垂直线l:x=m来作为分割直线。其中m为S中各点 x坐标的中位数。由此将S分割为S1和S2。 递归地在S1和S2上找出其最小距离d1和d2，并设 d=mind1,d2，S中的最接近点对或
8、者是d，或者是某个 p,q，其中pS1且qS2。 能否在线性时间内找到p,q？ v第一步筛选：如果最近点对由S1中的p3和 S2中的q3组成，则p3和q3一定在划分线L 的距离d内。 能否在线性时间内找到p3,q3 需要计算需要计算P1P1中的每个点与中的每个点与P2P2中的每个点的距离？中的每个点的距离？ v第二步筛选：考虑P1中任意一点p，它若与 P2中的点q构成最接近点对的候选者，则必 有distance(p，q)d。满足这个条件的P2 中的点一定落在一个d2d的矩形R中 并不必计算并不必计算P1P1中的每个点与中的每个点与P2P2中的每个点的距离！中的每个点的距离！O(nO(n 2 2
9、 ) ) R中的点具有稀疏性 u重要观察结论：P2中任何2个S中的点的距离 都不小于d。由此可以推出矩形R中最多只有6 个S中的点。 u重要结论：在分治法的合并步骤中最多只 需要检查6n/2=3n个候选点对！ R中最多只有6个S中的点 证明:将矩形R的长为2d的边3 等分，将它的长为d的边2等分 ，由此导出6个(d/2)(2d/3)的 矩形。 若矩形R中有多于6个S中的 点，则由鸽舍原理易知至少有 一个(d/2)(2d/3)的小矩形中有 2个以上S中的点。 设u，v是位于同一小矩形中 的2个点，则 distance(u,v)d。这与d的意义相矛盾。 * 鸽舍原理（也称抽屉原理） 把n+1个球，
10、放入n个抽屉，则一定有一个抽屉内至少有2个 球。 P2中与点p最接近这6个候选点的纵坐标与p 的纵坐标相差不超过d. 因此，若将P1和P2中所有S中点按其y坐标 排好序，则对P1中所有点，对排好序的点列 作一次扫描，就可以找出所有最接近点对的候 选者。对P1中每一点最多只要检查P2中排好 序的相继6个点。 如何确定要检查哪6个点 double cpair2(S) n=|S|; if (n 2) return ; 1、m=S中各点x间坐标的中位数; 构造S1和S2； /S1=pS|x(p)m 2、d1=cpair2(S1); d2=cpair2(S2); 3、dm=min(d1,d2); 4、设
11、P1是S1中距垂直分割线l的距离在dm之 内的所有点组成的集合； P2是S2中距分割线l的距离在dm之内所有 点组成的集合； 将P1和P2中点依其y坐标值排序； 并设X和Y是相应的已排好序的点列； 5、通过扫描X以及对于X中每个点检查Y中与 其距离在dm之内的所有点(最多6个)可以完成 合并； 当X中的扫描指针逐次向上移动时，Y中的 扫描指针可在宽为2dm的区间内移动； 设dl是按这种扫描方式找到的点对间的最 小距离； 6、d=min(dm,dl); return d; O(n) 2T(n/2 ) 常数时间 O(n) 常数时间 O(n) 复杂度分析 v、用了O(n)时间； v用了2T(n/2)
12、时间 v、用了常数时间 v在预排序的情况下用时O(n) 最接近点对问题最接近点对问题 u下面来考虑三维的情形。 选取一垂平面l:y=m来作为分割平面。其中m为S中各点 y坐标的中位数。由此将S分割为S1和S2。 递归地在S1和S2上找出其最小距离d1和d2，并设 d=mind1,d2，S中的最接近点对或者是d，或者是某个 p,q，其中pS1且qS2。 v第一步筛选：如果最近点对由S1中的p3和 S2中的q3组成，则p3和q3一定在划分平面 L的距离d内。 能否在线性时间内找到p3,q3 需要计算需要计算P1P1中的每个点与中的每个点与P2P2中的每个点的距离？中的每个点的距离？ v第二步筛选：
13、考虑P1中任意一点p，它若与 P2中的点q构成最接近点对的候选者，则必 有distance(p，q)d。满足这个条件的P2 中的点定落在一个d2d2d的长方体R中 并不必计算并不必计算P1P1中的每个点与中的每个点与P2P2中的每个点的距离！中的每个点的距离！O(nO(n 2 2 ) ) R中的点具有稀疏性 u重要观察结论：P2中任何2个S中的点的距离 都不小于d。由此可以推出长方体R中最多只有 24个S中的点。 u重要结论：在分治法的合并步骤中最多只 需要检查24n/2=12n个候选点对！ R中最多只有24个S中的点 distance(u,v)d。这与d的意义相矛盾。 由d的意义可知, P2
14、 中任何2个S中的 点的距离都不小于d. 由此可以推出长 方体R中最多只有24个S 中的点. 事实 上,我们可以将长方体C的长为2d的两 条边分别3等分和4等分,将它的长为d 的边2等分, 由此导出24个大小相等的( d /2) ( d /2) (2d /3) 的小长方体. 如 图3所示:若长方体C中有多于24个S中 的点,则由鸽舍原理易知至少有一个( d /2) ( d /2) (2d /3) 的小长方体中有2 个以上S中的点. 设u, v是这样2个点,它 们位于同一小长方体中, distance ( u, v) 为了确切地知道对于P1 中每个点p最多检查P2 中的哪24个点,我们 可以将点
15、p和P2 中所有S2的点投影到平面P: y = m上. 由于能与p点 一起构成最接近点对候选者的S2 中点一定在长方体R中,所以它们 在平面P上的投影点与点p在P上投影点的距离小于d. 由上面的分析 可知, 这种投影点最多只有24个. 因此,若将P1 和P2 中所有S的点依 次按其x坐标和z坐标排好序,则对P1 中任意点p而言,对已经按照x坐 标和z坐标排好序的点列作一次线性扫描,就可以找出所有最接近点 对的候选者. 设点q ( x, y, z) 为P2 中可以与P1 中的一点p ( x0 , y0 , z0 ) 构成候选点对的排好序的24个点中的一点,则满足x ( x0 - d, x0 +
16、d) , z ( z0 - d, z0 +d) ,即投影点在以p的投影点为中心的2d 2d的正方形区域中的点是我们要考察的候选点. 这就意味着我们 可以在O ( n) 时间内完成分治法的合并步骤. 如何确定要检查哪24个点 double spair (S ) n =| S | ; /| S | 表示S中点的个数3 / if ( n 2) return ; 1. m = S中各点y坐标的中位数; 利用平面P: y = m 划分构造子集S1 和S2 ; S1 = p S | y ( p) m 2. d1 = spair (S1 ) ; d2 = spair (S2 ) ; 3. dm = min ( d1 , d2 ) ; 4. 设P1 是S1 中距垂直分割面P
