生原因就在于排序时消耗了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