基于递归法的最接近点对问题

1、基于递归法的最接近 点对问题 姓名：杨 意学号： 309040102009 学院：数学信息学院专业：计算机辅助教 育 目录1、 问题综述 22、 用递归法解决 22.1 一维情形下的分 析 22.2 二维情形下的分 析 32.3 算法优化 63、结论 9基于递归法的最接近 摘要：在计算机应用 及几何对象的问题中 问题中，若将飞机作 这个空间中最近的一2.4 算法实现 6现现实世界中的实体。在涉 息。例如，在空中交通控制 大碰撞危险的两架飞机就是 本问题之一。本文就运用递点对问题中，常用诸如点、圆等简单的几何对象表，常需要了解其邻域中其他几何对象的信为空间中移动的一个点来处理，则具有最点。这类问

2、题是计算机几何学中研究的基 关键词：最接近点对 递归法 问题综述 最接近点对问题的提 法是：给定平面上 n 个点，找其中的一对点，使得在 n 个点组成的所 有点对中，该点对间 的距离最小。归法对一维和二维的情况加以讨论。实际情况下，最接近 点对可能多于一对，为简单起见 ，我 们只找其中的一对作 为问题的解。 有一个最直观的方法 就是将每一点与其他 n-1 个点的距离算出，找出达到最小距离的两点 即 可。然而，这样做 效率太低，我们想到用递归法来解决这个 问题。2、 用递归法解决将所给的平面上 n 个点的集合 S 分成两个子集 S1 和 S2 ，每个子集中约有 n/2 个点 。然 后在每个子集中

3、递归 地求其最接近的点对。在这里，一个关键 的问题是如何实现递归法中 的合并步骤，即由 S1 和 S2 的最接近点对，如何求 得原集合 S 中的最接近点对。如果组成 S 的最接近点对的两个点都在 S1 中或都在 S2 中，则问题很明显就可以找到答案。可是还 存在另外一种可能， 就是这两给点分别在 S1 和 S2 中的时候。下面主要讨论 这种情况。2.1 一维情形下的分 析为使问题易于理解和 分析，我们先来考虑一维的情形。此时， S 中的 n 各点退化为 x 轴上 的n个实数xl, x2, x3xn。最接近点对即为这 n个实数中相差最小的两个实数。我们尝试用递归法来求解， 并希望推广到二维的情形

4、。假设我们用x轴上的某个点 m将S划分为两个集合 S1和S2 ，使得S仁x S| x m 。这样一来，对于所有p 和q S2 有pv q。递归地在S1和S2上找出其最接近 点对p1 , p2和q1, q2，并设 d=min| p1- p2| ， | q1- q2|由此易知，S中的最接近进点对或者是 pl , p2，或者是 q1 , q2，或者是某个p3, q3, 其中，p3 S1且q3 S2。如图2-1-1所示。图 2-1-1 一维情形的递归法我们注意到，如果 S的最接近点对是p3, q3,即|p3-q3| v d,则p3和q3两者与m的距 离不超过 d，即 | p3-m| v d， | q3

5、 -m| v d。也就是说 ，p3 (m-d , m, q3 (m , m+d。由 于每个长度为 d 的半闭区间至多包含 S1 中的一个点，并且 m 是 S1 和 S2 的分割点，由图 2-1-1可以看出，如果(m-d , m中有S中点，则此点就是S1中最大点。同理，如果(m , m+d中有S中点，则此点就是 S2中最小点。因此，我们用线性时间就能找到区间(m-d , m和(m, m+d中所有点，即p3和q3。从而我们用线性时间就可以将S1的解和S2的解合并成为 S 的解。但是，还有一个问题 需要认真考虑，即分割点 m的选取，即S1和S2 的划分。选取分割 点m的一个基本要求 是由此将S进行分

6、割，使得 S= S1U S2 , S1M，S2 工，且51 x|x m 。容易看出，如果选取 m=max(S)+min(S)/2 ,可以满足分割要求。然而，这样选 取分割点，有可能造成划分出的子集 S1 和 S2 的不平衡 。例如在最 坏情况下, | S1|=1 , | S2 |=n-1 , 这样的计算效率与分割前相比提 高幅度不明显。这种现象 可以通过递归法中“ 平衡子问题”的方法加以解决。我们可以 适当选择分割点 m, 使 S1 和52 中有个数大致相等的点。我们会想到用 S 中各点坐标的中位数来作为分割 点。由此,我们设计出一 个求一维点集 S 的最接近点对的算法 Cpair1 如下：B

7、ool Cpair1(S,d)N=|S|;if(nv2)d= ;return false;m=S 中各点坐标的中位数；/ 构造 S1 和 S2 ；S仁x S | x m ;Cpair1(S1,d1);Cpair1(S2 ,d2);p=max(S1);q=min(S2 );d=min(d1,d2,q-p);return true2.2 二维情形下的分 析以上一维算法可以推 广到二维的情形。设S中的点为平面上的点，它们都有两个坐标值x和y。为了将平面上点集 S线性分割为大小大致相等 的两个子集 S1 和 S2 ,我们选取一垂直线 L：x=m 来作为分割直线。 其中，m为S中各点x坐标的中位数。由此

8、将S分割为S仁p S | x (p) w m 和S2 =p S| x (p) m 。从而使 S1 和 S2 分别位于直线 L 的左侧和右侧,且 S=S1U S2 。由于 m 是S中各x坐标的中位数，因此S1和S2中得点数大致相等。递归地在 S1 和 S2 上解最接近点对问题，我们分别得到 S1 和 S2 中的最小距离di和d2。现设d=mind1,d2。若S的最接近点对(p,q)之间的距离小于 d,贝U p和q必分属 于S1和S2 。不妨设p Si, q S2 。那么p和q距直线L的距离均小于d。因此，若 我们用P1和P2分别表示直线L的左边和右边的宽为 d的两个垂直长条区域，则p P1且 q

9、 P2,如图2-2-1所示。图 2-2-i 距直线 L 的距离小于 d 的所有点在一维情形下，距分割点距 离为d的两个区间(m-d, m和(m , m+d中最多各有S中一个点。因而这两点成为 唯一的未检查过的最接近点对候选者。二 维的情形则要复杂些。此时， P1中所有点和P2中所有点构成的点对均为最接近点对的候选者。在最坏的情况下有n2/4对这样的候选者。考 虑P1中任意一点p，它若与P2中的点q构成最接近点对的候选者，则必有distance(p,q) v d。满足这个条件的 P2中的点有多少个呢？容易看出这样的点一定 落在一个 d*2d 的矩形 R 中,如图 2-2-2 所示。图 2-2-2

10、 包含点 q 的 d*2d 矩形 R由d的意义可知，P2中任何两个S中的点的距离都不小于d。由此可以推出矩形 R中最多只有 6 个 S 中的点。下面我们来证明这个结论 。我们可以将矩形 R的长为2d的边3等分，将它的长为 d的边2等分，由此导出6个(d/2 ) * (2d/3 )的矩形。如图 2-2-3(a)所示。如图 2-2-3 矩形 R 中点的稀疏性若矩形R中有多于6个S中的点，则由鸽舍原 理易知至少有一个(d/2 ) * (2d/3 )的小 矩形中有 2 个以上 S 中的点。设 u, v 是这样 2 个点,它们位于同一小矩形中,则(x ( u) -x (v)2+ (y ( u) -y (

11、v) 2( d/2 ) 2+ (2d/3 ) 2=25/36d2因此，distance(u,v) 5d/6 v d。这与d的意义相矛盾。 也就是说矩形 R中最多只 有 6 个 S 中的点。图2-2-3 (b)是矩形中恰有6个S中点的极端情形。由于这种稀疏性质，对于P1中任意一点 p, P2 中最多只有 6 个点与它构成最接 近点对的候选者。因此, 在递归法的合并步骤 中,我们最多只需要 检查 6*n/2=3n 个候选者,而不是 n2/4 个候选者。我们将 p 和 P2 中所有 S2 的点投影到垂直线 L 上。由于能与 p 点一起构成 最接近点对候 选者的S2中点一定在矩 形R中，所以它们在直线

12、L上的投影点距p在L上投影点的距离小于d。由上面的分析可知，这种投影点最多只有6个。因此，若将 P1和P2中所有S中点按其 y 坐标排好序 ,则对 Pi 中所有点,对排 好序的点列做一次扫描,就可以 找出所有最 接近点对的候选者。对P1中每一点最多只要检查 P2中排好序的相继6个点。至此,我们给出用递 归法求二维点集最接近点对的算法 Cpair 2 如下：bool Cpair 2(S,d)N=|S|;If(n2)d=g;Return false;i. m=S 中各点 x 间坐标的中位数； 构造 S1 和 S2 ；/S1=p S| x(p)m 2. Cpair2(S1,d1);Cpair2(S2

13、 ,d2);3 . dm=min(d1,d2);4 . 设 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 tr

14、ue ；2.3 算法优化在以上二维情形下的 算法中，在每次执行第 4 步时都要进行排序， 这将花费较多的时间， 从而增加算法的复杂 度。因此，在这里我们要作一个技术处理 。我们采用设计算法时常用 的预排序技术，在使 用递归法之前，预先将 S 中 n 个点依其 y 坐标值排好序，设排好序的 点列为P*。在执行递归法的第4步时，只要对P*作一次线性扫描，即可抽取出我们所需要 的排好序的点列 X和Y。然后，在第5步时再对X作一次线性扫描，即可求得dl。2.4算法实现在具体实现算法 Cpair 2 时，我们分别用类 Point X 和 Point Y 表示依 x 坐标和依 y 坐标 排序的点。Clas

15、sPoint XPublic:Int operator=(Point X a) constreturn (x=a.x);Private:Int ID; /点编号Float x,y; / 点坐标;ClassPoint YPublic:int operator=(Point Ya) constreturn (y=a.y)Private:Int p; / 同一点在数组 X 中的坐标Float x,y; / 点坐标；平面上任意两点 u 和 v 之间的距离可计算如下：Template Inline float distance(const Type& u,const Type& v)Float dx=u

16、.x-v.x;Float dy=u.y-v.y;Return sqrt(dx * dx +dy * dy);在算法Cpair 2中，用数组X存储输入的点集。在算法的预处理阶段，将数组 X中的点依 x 坐标和依 y 坐标排序，排好序的点集 分别存储在数组 X 和数组 Y 中。事实上，我们 只要取m=(L+r)/2 ,则XL:m和Xm+1:r就是满足要求的分割。依y坐标排好序的数组 Y用于在算法的合并步中 快速检查 d 矩形条内最接近点对的候选者。 Bool Cpair2(Point XX,int n,Point X&a,Point X&b,float&d)If(n2) return false;

17、MergeSort(X,n);Point Y* Y=new Point Y n;For (int i =0;i n; i+)/将数组X中的点复制到数组Y中Yi.p = i ;Yi.x =Xi.x ;Yi.y =Xi.y ;MergeSort (Y,n);Point Y* Z= new Point Y n;Closest (X,Y,Z,0,n-1 ,a,b,d);delete Y;delete Z; return true;算法 Cpair2 中，具体计算最接近点对的工 作由函数 closest 完成。Viod closest (Point X X, Point YY, Point YZ,int

18、 L,int r,Point X&a,Point X&b,float&d) If (r - 1 = = 1)/2 点的情形a= XL; b=Xr;d =distance(XL,Xr);return;If(r - 1 = =2)3点的情形Float d1 = distance (XL,XL+1);Folat d2 = distance (XL+1,Xr);Float d3 = distance (XL,Xr);If (dL= d2 & dL=d3) a= XL; b =XL+1 ; d =dL;return;If (d2=d3)a= XL+1; b= Xr;d = Xd2;else a= XL;b =Xr;d =d3; return; / 多于 3 点的情形，用递归法Int