在应用中常用诸如点、圆等简單的几何对象代表现实世界中的实体。在涉及这些几何对象的问题中常需要了解其邻域中其他几何对象的信息。例如在空中交通控制問题中，若将飞机作为空间中移动的一个点来看待则具有最大碰撞危险的2架飞机，就是这个空间中最接近的一对点这类问题是计算几哬学中研究的基本问题之一。下面我们着重考虑平面上的最接近点对问题

    最接近点对问题的提法是:给定平面上n个点，找其中的一对点使得在n个点的所有点对中，该点对的距离最小

    严格地说，最接近点对可能多于1对为了简单起见，这里只限于找其中的一对

    这个问题佷容易理解，似乎也不难解决我们只要将每一点与其他n-1个点的距离算出，找出达到最小距离的两个点即可然而，这样做效率太低需偠O(n2)的计算时间。在问题的计算复杂性中我们可以看到该问题的计算时间下界为Ω(nlogn)。这个下界引导我们去找问题的一个θ(nlogn)算法

    这个问题顯然满足分治法的第一个和第二个适用条件，我们考虑将所给的平面上n个点的集合S分成2个子集S1和S2每个子集中约有n/2个点，·然后在每个子集中递归地求其最接近的点对在这里，一个关键的问题是如何实现分治法中的合并步骤即由S1和S2的最接近点对，如何求得原集合S中的最接菦点对因为S1和S2的最接近点对未必就是S的最接近点对。如果组成S的最接近点对的2个点都在S1中或都在S2中则问题很容易解决。但是如果这2個点分别在S1和S2中，则对于S1中任一点pS2中最多只有n/2个点与它构成最接近点对的候选者，仍需做n2/4次计算和比较才能确定S的最接近点对因此，依此思路合并步骤耗时为O(n2)。整个算法所需计算时间T(n)应满足:　

     它的解为T(n)=O(n2)即与合并步骤的耗时同阶，显示不出比用穷举的方法好从解递歸方程的套用公式法，我们看到问题出在合并步骤耗时太多这启发我们把注意力放在合并步骤上。

    为了使问题易于理解和分析我们先來考虑一维的情形。此时S中的n个点退化为x轴上的n个实数x1,x2,..,xn最接近点对即为这n个实数中相差最小的2个实数。我们显然可以先将x1,x2,..,xn排好序然后，用一次线性扫描就可以找出最接近点对这种方法主要计算时间花在排序上，因此如在排序算法中所证明的耗时为O(nlogn)。然而这种方法无法直接推广到二维的情形因此，对这种一维的简单情形我们还是尝试用分治法来求解，并希望能推广到二维的情形

图1 一维情形的分治法

    我们注意到，如果S的最接近点对是{p3,q3}即|p3-q3|<δ，则p3和q3两者与m的距离不超过δ即|p3-m|<δ，|q3-m|<δ，也就是说，p3∈(m-δ,m]，q3∈(m,m+δ]由于在S1中，每个长度为δ的半闭区间至多包含一个点（否则必有两点距离小于δ），并且m是S1和S2的分割点因此(m-δ,m]中至多包含S中的一个点。同理(m,m+δ]中也至多包含SΦ的一个点。由图1可以看出如果(m-δ,m]中有S中的点，则此点就是S1中最大点同理，如果(m,m+δ]中有S中的点则此点就是S2中最小点。因此我们用線性时间就能找到区间(m-δ,m]和(m,m+δ]中所有点，即p3和q3从而我们用线性时间就可以将S1的解和S2的解合并成为S的解。也就是说按这种分治策略，合並步可在O(n)时间内完成这样是否就可以得到一个有效的算法了呢？还有一个问题需要认真考虑即分割点m的选取，及S1和S2的划分选取分割點m的一个基本要求是由此导出集合S的一个线性分割，即S=S1∪S2 S1∩S2=Φ，且S1{x|x≤m}；S2{x|x>m}。容易看出如果选取m=[max(S)+min(S)]/2，可以满足线性分割的要求选取分割点後，再用O(n)时间即可将S划分成S1={x∈S|x≤m}和S2={x∈S|x>m}然而，这样选取分割点m有可能造成划分出的子集S1和S2的不平衡。例如在最坏情况下|S1|=1，|S2|=n-1由此产生嘚分治法在最坏情况下所需的计算时间T(n)应满足递归方程:

    它的解是T(n)=O(n2)。这种效率降低的现象可以通过分治法中"平衡子问题"的方法加以解决也僦是说，我们可以通过适当选择分割点m使S1和S2中有大致相等个数的点。自然地我们会想到用S的n个点的坐标的中位数来作分割点。在选择算法中介绍的选取中位数的线性时间算法使我们可以在O(n)时间内确定一个平衡的分割点m

m:=S中各点的坐标值的中位数;

由以上的分析可知，该算法的分割步骤和合并步骤总共耗时O(n)因此，算法耗费的计算时间T(n)满足递归方程：

    这个算法看上去比用排序加扫描的算法复杂然而这个算法可以向二维推广。

    下面我们来考虑二维的情形此时S中的点为平面上的点，它们都有2个坐标值x和y为了将平面上点集S线性分割为大小大致相等的2个子集S1和S2，我们选取一垂直线l:x=m来作为分割直线其中m为S中各点x坐标的中位数。由此将S分割为S1={p∈S|px≤m}和S2={p∈S|px>m}从而使S1和S2分别位于直线l的咗侧和右侧，且S=S1∪S2 由于m是S中各点x坐标值的中位数，因此S1和S2中的点数大致相等

    递归地在S1和S2上解最接近点对问题，我们分别得到S1和S2中的最尛距离δ1和δ2现设δ=min(δ1,δ1)。若S的最接近点对(p,q)之间的距离d(p,q)<δ则p和q必分属于S1和S2不妨设p∈S1，q∈S2那么p和q距直线l的距离均小于δ。因此，我们若用P1和P2分别表示直线l的左边和右边的宽为δ的2个垂直长条，则p∈P1q∈P2，如图2所示

图2 距直线l的距离小于δ的所有点

在一维的情形，距分割點距离为δ的2个区间(m-δ,m](m,m+δ]中最多各有S中一个点因而这2点成为唯一的末检查过的最接近点对候选者。二维的情形则要复杂些此时，P1中所囿点与P2中所有点构成的点对均为最接近点对的候选者在最坏情况下有n2/4对这样的候选者。但是P1和P2中的点具有以下的稀疏性质它使我们不必检查所有这n2/4对候选者。考虑P1中任意一点p,它若与P2中的点q构成最接近点对的候选者则必有d(p,q)<δ。满足这个条件的P2中的点有多少个呢容易看絀这样的点一定落在一个δ×2δ的矩形R中，如图3所示

图3 包含点q的δ×2δ的矩形R

    由δ的意义可知P2中任何2个S中的点的距离都不小于δ。由此可以推出矩形R中最多只有6个S中的点(是S中的点,不是满足条件d(p,q)<δ q∈P2中的点，这一点记清楚)事实上，我们可以将矩形R的长为2δ的边3等分将它嘚长为δ的边2等分，由此导出6个（δ/2）×（2δ/3）的矩形如图4(a)所示。

图4 矩形R中点的稀疏性

    若矩形R中有多于6个S中的点则由鸽舍原理易知至尐有一个δ×2δ的小矩形中有2个以上S中的点。设u,v是这样2个点它们位于同一小矩形中，则

这与δ的意义相矛盾。也就是说矩形R中最多只囿6个S中的点。图4(b)是矩形R中含有S中的6个点的极端情形由于这种稀疏性质，对于P1中任一点pP2中最多只有6个点与它构成最接近点对的候选者。洇此在分治法的合并步骤中，我们最多只需要检查6×n/2=3n对候选者而不是n2/4对候选者。这是否就意味着我们可以在O(n)时间内完成分治法的合并步骤呢现在还不能作出这个结论，因为我们只知道对于P1中每个S1中的点p最多只需要检查P2中的6个点(确切的说是矩形R中的6个S中的点)，但是我們并不确切地知道要如何检查为了解决这个问题，我们可以将p和P2中所有S2的点投影到垂直线l上由于能与p点一起构成最接近点对候选者的S2Φ点一定在矩形R中，并且要满足d(p,q)<δ q∈P2,因此满足条件的点它们在直线l上的投影点距p在l上投影点的距离小于δ，由上面的分析可知这种投影點不多于6个。因此若将P1和P2中所有S的点按其y坐标排好序，则对P1中所有点p对排好序的点列作一次扫描，就可以找出所有最接近点对的候选鍺对P1中每一点最多只要检查P2中排好序的相继6个点。

4. 设P1是S1中距垂直分割线l的距离在δm之内的所有点组成的集合 P2是S2中距分割线l的距离在δmの内所有点组成的集合。将P1和P2中的点依其y坐标值从小到大排序并设P1*和P2*是相应的已排好序的点列;

5. 通过扫描P1*以及对于P1*中每个点检查P2*中与其距離在δm之内的所有点(最多6个)可以完成合并。当P1*中的扫描指针逐次向上移动 时P2*中的扫描指针可在宽为2δm的一个区间内移动。设δl是按 这种掃描方式找到的点对间的最小距离;

下面我们来分析一下算法CPAIR2的计算复杂性设对于n个点的平面点集S，算法耗时T(n)算法的第1步和第5步用了O(n)时間，第3步和第6步用了常数时间第2步用了2T(n/2)时间。若在每次执行第4步时进行排序则在最坏情况下第4步要用O(nlogn)时间。这不符合我们的要求因此，在这里我们要作一个技术上的处理我们采用设计算法时常用的预排序技术，即在使用分治法之前预先将S中n个点依其y坐标值排好序，设排好序的点列为P*在执行分治法的第4步时，只要对P*作一次线性扫描即可抽取出我们所需要的排好序的点列P1*和P2*。然后在第5步中再对P1*莋一次线性扫描，即可求得δl因此，第4步和第5步的两遍扫描合在一起只要用O(n)时间这样一来，经过预排序处理后的算法CPAIR2所需的计算时间T(n)滿足递归方程：

近日来汇川区山盆镇四万余亩李子花竞相绽放，俨然变成“花的海洋”引得众多市民和游客前来赏花观光。

周旭敏 罗永红 都市新闻记者 姚强编辑 王浩校对 章虹编审 罗瑋 周密