分治法Sch1-4S1S2qlq2plp2p3m如果S的最接近点对是p3,q3)，即|p3-q3|<d，则p3和q3两者与m的距离不超过d，即p3E（m-d,ml，q3E（m，m+d)。由于在S1中，每个长度为d的半闭区间至多包含一个点（否则必有两点距离小于d），并且m是S1和S2的分割点，因此（m-d,m中至多包含S中的一个点。由图可以看出，如果（m-d,ml中有S中的点，则此点就是S1中最大点·因此，我们用线性时问就能找到区间（m-d，m和（m，m+dl中所有点，即P3和q3。从而我们用线性时问就可以将S1的解和S2的解合并成为S的解。6
6 Sch1-4 分治法 如果S的最接近点对是{p3,q3}，即|p3-q3|<d，则p3和q3两者与m的距离 不超过d，即p3∈(m-d,m]，q3∈(m,m+d]。 ◆由于在S1中，每个长度为d的半闭区间至多包含一个点（否则必有两点距 离小于d），并且m是S1和S2的分割点，因此(m-d,m]中至多包含S中的一 个点。由图可以看出，如果(m-d,m]中有S中的点，则此点就是S1中最大点。 ◆因此，我们用线性时间就能找到区间(m-d,m]和(m,m+d]中所有点，即 p3和q3。从而我们用线性时间就可以将S1的解和S2的解合并成为S的解
Sch1-4 分治法>选取一垂直线l：X=m来作为分割直线。其中m为S中各点x坐标的中位数。由此将S分割为S1和S2。>递归地在S1和S2上找出其最小距离dl和d2，并设d=minfdl.d2h，S中的最接近点对或者是d，或者是禁个[p,q，其中pEP1且qEP2。>能否在线性时间内找到p.q?dC12S1S2P1P2
7 Sch1-4 分治法 ➢选取一垂直线l:x=m来作为分割直线。其中m为S中各点x坐标的中位数。由 此将S分割为S1和S2。 ➢递归地在S1和S2上找出其最小距离d1和d2，并设d=min{d1,d2}，S中的最接 近点对或者是d，或者是某个{p,q}，其中p∈P1且q∈P2。 ➢能否在线性时间内找到p,q？
分治法Sch1-4能否在线性时间内找到p,q?考虑P1中任意一点p，宅若与P2中的点构成最接近点对的候选者，则必有distance(pq)<d。满足这个条件的P2中的点一定落在一个d×2d的矩形R中·由d的意义可知，P2中任何2个S中的点的距离都不小于d。由此可以推出矩形R中最多只有6个5中的点。·因此，在分治法的合并步骤中最多只需要检查6×n/2=3n个候选者0证明：将矩形R的长为2d的边3等分，将宅的长为dC的边2等分，由此导出6个（d/2）×（2d/3）的矩形。若矩形R中有多于6个S中的点，则由鸽舍原理易知32至少有一个（d/2）×（2d/3）的小矩形中有2个以上S中R的点。设u，V是位于同一小矩形中的2个点，则NrrOdistance（u,v)<d。这与d的意义相矛盾。P1P2(b)(a)8
8 Sch1-4 分治法 考虑P1中任意一点p，它若与P2中的点q构成最接近点对的候选者，则必有distance(p， q)＜d。满足这个条件的P2中的点一定落在一个d×2d的矩形R中 ◆由d的意义可知，P2中任何2个S中的点的距离都不小于d。由此可以推出矩形R中最多 只有6个S中的点。 ◆因此，在分治法的合并步骤中最多只需要检查6×n/2=3n个候选者 能否在线性时间内找到p,q？ 证明:将矩形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的意义相矛盾
Sch1-4 分治法为了确切地知道要检查哪6个点，可以将P和P2中所有S2的点投影到垂直线上。由于能与P点一起构成最接近点对候选者的S2中点一定在矩形R中，所以宅们在直线I上的投影点距P在1上投影点的距离小于d。由上面的分析可知，这种投影点最多只有6个。因此，若将P1和P2中所有S中点按其y坐标排好序，则对P1中所有点，对排好序的点列作一次扫描，就可以找出所有最接近点对的候选者。对P1中每一点最多只要检查P2中排好序的相继6个点
9 ⚫ 为了确切地知道要检查哪6个点，可以将p和P2中所有S2的点投影 到垂直线l上。由于能与p点一起构成最接近点对候选者的S2中点 一定在矩形R中，所以它们在直线l上的投影点距p在l上投影点的距 离小于d。由上面的分析可知，这种投影点最多只有6个。 ⚫ 因此，若将P1和P2中所有S中点按其y坐标排好序，则对P1中所有 点，对排好序的点列作一次扫描，就可以找出所有最接近点对的 候选者。对P1中每一点最多只要检查P2中排好序的相继6个点。 Sch1-4 分治法
分治法Sch1-4double cpair2(S)4、设P1是S1中距垂直分割线l的距离在dm之内t的所有点组成的集合：P2是S2中距分割线l的距离在dm之内所有点组n=|SI:成的集合；将P1和P2中点依其y坐标值排序；if (n<2)return并设X和Y是相应的己排好序的点列1、m=S中各点x间坐标的中位数；5、通过扫描X以及对于X中每个点检查Y中与其距离在dm之内的所有点（最多6个）可以完成合并；构造S1和S2;当X中的扫描指针逐次向上移动时，Y中的扫描//S1=(p ES|x(p)<=m)指针可在宽为2dm的区间内移动设dl是按这种扫描方式找到的点对问的最小距S2=(pES|×(p)>m)离；2、 d1=cpair2(S1);6、d=min(dm,dl);return d;d2=cpair2(S2);}3. dm=min(d1,d2);时间复杂度：T(n)=O(nlogn）0(1)n<4T(n)=(2T(n/2)+O(n) n≥410
10 Sch1-4 分治法 double cpair2(S) { n=|S|; if (n < 2) return ; 1、m=S中各点x间坐标的中位数; 构造S1和S2； //S1={p∈S|x(p)<=m}, S2={p∈S|x(p)>m} 2、d1=cpair2(S1); d2=cpair2(S2); 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 d; } 时间复杂度：T(n)=O(nlogn) + = 4 4 2 ( / 2) ( ) (1) ( ) n n T n O n O T n