三维空间的最接近点对问题

三维空间的最接近点对问题

刘志辉

（中国民航大学 天津 300300）

摘要：最接近点对问题的求解就是在点集空间中求解最接近的一对点的距离。本文利用分治策略并结合预排序和分层映射技术把一维、二维情况下的最接近点对问题推广至三维，使问题在O(n?logn)时间内得以解决，相对时间复杂度为

O(n2)的普通方法而言，效率得到很大的提高。 关键词：最接近点对；鸽舍原理；分层映射；

在文献[1]中，对一维和二维情况下的最接近点问题的求解进行了详细描述，于是引起了人们对三维情况下的最接近点对问题的关注。文献[2]中，提出了一种对三维最接近点对问题的求解方法：先对三维空间的点集进行两次预排序，利用与二维情况下相类似的合并算法，在O(n?logn)时间内求出最接近的点对。但是其合并过程所采用的算法不明确，令人质疑。本文只需对空间点集进行一次预排序，然后在合并过程中采用分层映射技术使其在O(n)的时间内完成合并，从而整个算法的时间复杂度为O(n?logn)，并且算法思路清晰。可以证明在渐近意义下，此算法已是最优算法。

一、一维和二维情况下的最接近点对问题

把一维情况下点集S中的n个点退化为x轴上的n个实数x1,x2,...,xn。于是最接近点对即为这n个实数中相差最小的两个实数。显然可以先将这n个实数排序好，映射到x轴上，然后用x轴上某个点m将S划分为大小大致相等的两个子集合S1和S2，且S1??x?S|x?m?；S2??x?S|x?m?，如图1所示。于是求S中的最接近点对转变为分别求S1、S2中的最接近点对和其合并后的最接近点对。如果已求得S1和S2中的最小点对距离分别为d1和d2，合并时只需O(1)时间就能求得合并时的最接近点对，即S1和S2中分别离点m最近的一个点，如图1中的点pm和qm。这样S中的最接近点对的距离为d?max?d1,d2,|pm?qm|?。从而一

维情况下只需用一次线性扫描就可以找出最接近点对，算法中主要计算时间花费

在排序上，总的时间为o(n*logn)。

S1 m p q S2 图1 一维情况的最接近点对分治法

二维情况下的最接近点对可以表述为求xy平面中最接近的点对。先对平面中所有点按照x坐标进行排序，用S记排序后的点集，求出所有点x坐标值的中位数，记为m，然后用直线l:x?m把点集S划分为大致相等的两个子集S1和S2，

且S1??p?S|x(p)?m?；S2??p?S|x(p)?m?。这样把求S中的最接近点对转变

为分别求S1、S2中的最接近点对和其合并后的最接近点对。子集中的最接近点对可以递归求得，但合并时最接近点对的求解比一维情况下要复杂些。设d1和d2分别为S1和S2中的最小距离，设d?min?d1,d2?。在合并时，对于S中距离小于d的两点p和q必定满足：p和q分别属于S1和S2，在此设p?S1，q?S2；令P1和

P2分别表示距直线l的左边和右边的宽为d的两个区间，则p?P1，q?P2，如图2左所示。按照正常思维，P1中的所有点和P2中的所有点在最坏情况下有n2/4对最接近点对的候选者，但是P1和P2中的点具有稀疏性质，使得不必检查所有这

n2/4个候选者，而最多只需要检查6?n/2?3n个候选者。P1和P2中的点的稀疏

性表现在：对于P1中的任意一点p，P2中与其构成最接近点对的候选者的点必定落在一个d?2d的矩形R中，如图2左所示；利用鸽舍原理，R中这样的候选点最多只有6个，如图2右所示，6个虚线矩形中每个矩形中最多只有一个候选点，具体描述可以参考文献[1]。因此，将P1和P2和中所有中点按其坐标y排好序，则对P1中所有点最多只要检查P2中排好序的相继6个点。但此时合并的计算复杂

度需要O(n?logn)，并不是O(n)，没有达到预想的效果，不过可以通过在求解问题之前，把S中的点按其坐标y进行预排序来解决。所以二维情况下的最接近点对可以在的O(n?logn)时间内求得。

P1 P2 2d/3 p R d d d d d/2 d/2 2d/3 2d/3

图2二维情况的最接近点对分治法

二、最接近点对问题的三维推广

有了一维和二维的最接近点对描述，可以依此推广到三维。对于三维空间，所有的点有xyz三个坐标。于是三维情况下的最接近点对可以表述为求xyz空间中最接近的点对。 1、 问题描述

先对三维空间中所有点按照y坐标进行排序，用S记排序后的点集。求出所有点y坐标值的中位数，记为m，然后用平面l:y?m把点集S划分为大致相等的两个子集S1和S2，且S1??p?S|y(p)?m?；S2??p?S|y(p)?m?。这样把求

S中的最接近点对转变为分别求S1、S2中的最接近点对和其合并后的最接近点

对。然后依此方法递归地在S1和S2中求解最接近点对，设d1和d2分别为S1和S2中的最小距离，设d?min?d1,d2?。但求解合并时最接近点对比一维和二维都要复杂得多，成为问题求解的难点。

合并时，对于S中距离小于d的两点p和q必定满足：p和q分别属于S1和

S2，在此设p?S1，q?S2。那么p和q距平面的距离均小于d。因此，若令P1和则p?P1，q?P2，P2分别表示距平面l的左边和右边的宽为d的两个长条形区间，

如图3左所示。此时，P1中的所有点和P2中的所有点在最坏情况下有n2/4对最接近点对的候选者。但是P1和P2中的点与二维情况下具有类同的稀疏性质，使得不必检查所有这n2/4个候选者。P1和P2中的点的稀疏性表现在：对于P1中的任意一点p，P2中与其构成最接近点对的候选者的点必定落在一个d?2d?2d的长方体R中，如图3左所示；利用鸽舍原理，R中这样的候选点最多只有24个[2]，如图3右所示，24个虚线小长方体中每个长方体中最多只有一个候选点。因为对于如图3右中，每一个小长方体(d/2)?(2d/3)?(d/2)中如果有2个以上S中的点，设u和v是这样的2个点，则

(x(u)?x(v))2?(y(u)?y(v))2?(z(u)?z(v))2?172d 18 因此，dist(u,v)?d，这与前面d的意义相矛盾。也就是说长方体R中最多只有24个S中的点，其实数字24并不重要，重要的是长方体R中最多只有常数个这样的点。因此，在分治法的合并过程中，最多只需要检查24?n/2?12n个候选者，而不n2/4个候选者。在此并不能意味着可以在O(n)时间内完成分治法的合并过程，因为对于P1中的任意一点，我们并不确切知道要检查P2中哪24个点。

图3三维情况的最接近点对分治法

2、 分层映射和预排序

为了解决以上合并过程中遇到的问题，在[2]中先将P1和P2中的所有点按其x坐标排好序，然后对排好序的P1和P2再进行z坐标排序，也就是在此进行两次排序。令经过这样的两次排序后，P1和P2变为Z1和Z2。这时对于Z1中的每一点最多只要检查Z2中的相继24个点，因此对于Z1中所有点，作一次扫描，就可以在

Z2中找出所有最接近点对的候选者。但这种方法令人质疑，且要经过两次排序，在空间点数很大时，效率提高得不明显。

相对上面的不足，分层映射显出了它的优越性。在合并时，先对于P1和P2中的所有点顺z轴方向分层映射到长为2d的长条形区域内，然后分别对各层中P1和P2中的点按其x坐标排序。接着对每一层中排好序的P1中的点只需检查同层中排好序的P2中的相继24个点，因此对于排好序的P1中所有点，逐层扫描，通过一次扫描，就可以在排好序的P2中找出所有最接近点对的候选者。具体的分层映射过程为：找出P1和P2的合集中z坐标值最小的点o；从o点开始，顺着z轴，每间距2d作一平行于xoy面的分割面，如此分割到P1和P2的合集中z坐标值最大的点或包括z坐标值最大的点终止。这时，P1和P2中的所有点就分别被映射到分割的长条形区域中，每一层可以用一个数组来保存所映射的点集。在此还要注意一个问题，在前面讨论P1和P2中的点的稀疏性质时，要求对于P1中的任意一点p，

P2中与其构成最接近点对的候选者的点必定落在以从p点引出的一条垂直于分割平面l的直线为中心轴的一个d?2d?2d的长方体R中，而P1中的点并不能保证都位于每一层的中平面上，所以对于每层中非中心平面上的P1中的点，还必须要投影到相邻的分割层中。投影的原则为：中心平面以上的点投影到与该层上相邻的分割层中；中心平面以下的点投影到与该层下相邻的分割层中。

很容易发现，采用以上分层映射技术和排序的方法来完成合并，在最坏情况下其计算复杂度需要O(n?logn)，并不是O(n)，因此这种效果是不理想的。产

生原因就在于排序时消耗了O(n?logn)的时间。这时我们可以采用二维情况下的最接近点对的预排序技术来降低合并时排序所耗费的不必要的时间，使合并在的

O(n)时间内完成，即在问题求解之前对中的所有点进行一次x坐标预排序。

3、 分层轴的选取

对于三维情况下的最接近点对问题的求解还牵涉到一个分层轴的选取过程。令V为包含三维空间中所有点的最小边界长方体，dx为V在x轴方向的长度，dy为V在y轴方向的长度，dz为V在z轴方向的长度。那么选取min?dx,dy,dz?的方向轴为分层轴，这样有利于减少分层层次，降低分层的时空开销。对于dx、dy和

dz值差不多的情况，任意选取一个坐标轴作为分层轴。 4、 算法伪代码描述

结合以上描述，用分治法求三维点集最接近点对的算法Cpair3如下： bool Cpair(S,d) {

n=|S|; if(n<2){ }

SelestAxis(S,x,y,z); //选取分层轴,在此设选取的分层轴为Z轴

d= ?; return false;

X=SortX(S); //对S中所有点进行X坐标排序 Y=SortY(S); //对S中所有点进行Y坐标排序 Cpair(X,Y,d,n); return true; }

void Cpair(X,Y,d,n) {

if(n<2){

}

d= ?; return ;

m=Y中各点y坐标的中位数;

构造Y1和Y2; // Y1??p?Y|y(p)?m?,Y2??p?Y|y(p)?m?

Cpair(X,Y1,d1,n/2); Cpair(X,Y2,d2,n-n/2); dm=min(d1, d2);

结合预排序X，构造P1和P2，并对P1和P2中所有点顺Z轴进行分层映射;

//P1??p?Y1||y(p)?m|?dm?,P2??p?Y2||y(p)?m|?dm?

逐层扫描每一层，对每层中P1中的每个点检查同层的P2中与其距离在dm

之内的所有点;

按照上述扫描方式找到的最近点对的距离dn; d=min{dm,dn}; }

5、 算法效率

由前面的问题描述可知，整个问题的求解过程需要两次排序，一次用于分治划分，一次用于合并时的点对扫描，所以用于排序的时间为O(n?logn)。由于在合并过程中消耗时间为O(n)，因此用分治法求解问题所耗费的时间T(n)可以用下式表达：

?O(1)T(n)???2T(n/2)?O(n)n?4 n?4计算得出T(n)?O(nlogn)，结合排序时所消耗的时间，整个算法可以在

O(n?logn)时间内完成。

三、总结

三维情况下的最接近点对问题在日常生活中经常遇到，特别是在民航的空中管制工作中。本文采用预排序和分层映射技术，使问题可以在O(n?logn)的时间

内得到解决，相对时间复杂度为O(n2)的普通方法而言，效率得到很大的提高。但同时也会发现时间效率的提高是以分层映射时的空间消耗为代价的。在侧重时间效率而空间复杂度要求不高时，该算法显现出了巨大的优势。

参考文献：

[1] 王晓东．计算机算法设计与分析(第三版)．电子工业出版社．2007

[2] 张晓红，胡金初．分治法实现最接近点对问题的三维推广算法．山西师范大学学报．2006

本文来源：https://www.bwwdw.com/article/tr76.html