（转）最接近点对算法

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

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

T(n)=2T(n/2)+O (n² )

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

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

    假设我们用x轴上某个点m将S划分为2个子集S₁ 和S₂ ，使得S₁ ={x∈S|x≤m}；S₂ ={x∈S|x>m}。这样一来，对于所有p∈S₁ 和q∈S₂ 有p<q。

    递归地在S₁ 和S₂ 上找出其最接近点对{p₁ ,p₂ }和{q₁ ,q₂ }，并设δ =min{|p₁ -p₂ |,|q₁ -q₂ |}，S中的最接近点对或者是{p₁ ,p₂ }，或者是{q₁ ,q₂ }，或者是某个{p₃ ,q₃ }，其中p₃ ∈S₁ 且q₃ ∈S₂ 。如图1所示。

 

图1 一维情形的分治法

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

   T(n)=T(n-1)+O (n)

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

    至此，我们可以设计出一个求一维点集S中最接近点对的距离的算法CPAIR1如下。

function CPAIR1(S);
begin
  if |S|=2 then δ=|x[2]-x[1]| // x[1..n]存放的是S中n个点的坐标
           else if (|S|=1) 
                   then δ:=∞
                   else begin
                          m:=S中各点的坐标值的中位数;
                          构造S1和S2,使S1={x∈S|x≤m}，S2={x∈S|x>m};
                          δ1:=CPAIRI(S1);
                          δ2:=CPAIRI(S2);
                           p:=max(S1);
                           q:=min(S2);
                          δ:=min(δ1,δ2,q-p);
                        end;
  return(δ);
end;

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

    解此递归方程可得T (n )=O (n logn )。

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

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

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

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

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

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

由δ 的意义可知P₂ 中任何2个S中的点的距离都不小于δ 。由此可以推出矩形R中最多只有6个S中的点。事实上，我们可以将矩形R的长为2δ 的边3等分，将它的长为δ 的边2等分，由此导出6个（δ /2）×（2δ/3） 的矩形。如图4(a)所示。

图4 矩形R中点的稀疏性

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

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

    至此，我们可以给出用分治法求二维最接近点对的算法CPAIR2如下:

function CPAIR2(S);
begin
  if |S|=2 then δ:=S中这2点的距离
     else if |S|=0 
           then δ:=∞
           else begin
                 1.  m:=S中各点x坐标值的中位数;
                     构造S1和S2，使S1={p∈S|px≤m}和S2={p∈S|px>m}
                 2.  δ1:=CPAIR2(S1);δ2:=CPAIR2(S2);
                 3.  δm:=min(δ1,δ2);
                 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是按
                     这种扫描方式找到的点对间的最小距离;
                 6.  δ=min(δm,δl);
               end;
  return(δ);
end;

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

    显而易见T(n)=O (n logn )，预排序所需的计算时间为O (n 1ogn )。因此，整个算法所需的计算时间为O (n logn )。在渐近的意义下，此算法已是最优的了。

 

个人认为算法其实并不难，只是作者的文字表达功力和严谨的思维和一步步深入解决问题的能力相当值得学习