基于分治法的三维最近点对问题的研究

林泽瀚

（广州大学 数学与信息科学学院，广东广州 510006）

0 引言

分治法在计算机科学领域中占据着重要的地位。这个思想被应用于多种重要的算法设计中，如快速排序、归并排序、快速傅里叶算法等。最近点对问题是计算几何领域的研究的重点问题，常常应用于大数据计算与空中交通的计算机自动控制系统中。目前，研究方向已经往高维空间下发展[1-5]。

本文所讨论的问题可以描述为：给定个点，找出其中的一对点的距离，使得在这个点的所有点对中，该距离为所有点对中最小的。在实际情况中，可能会出现不止一个最近点对的情况，或者出现浮点误差。为了规范化问题，我们只考虑得到在一定浮点误差内准确的答案即可。

1 相关工作

1.1 二维最近点对朴素做法

（1）算法描述

对于二维最近点对的问题, 我们有朴素的做法: 维护一个最小值，直接对任意两个点，检验它们是否能够构成最小值，不断更新答案，最终得到的就是最近点对距离。

（2）朴素做法的伪代码表示

基于上文的分析，可以得到朴素做法的伪代码如图1所示：

图1 朴素做法的伪代码

（3）时间复杂度分析

分析上述算法,其中min函数是取两者的最小值，distance函数是计算两点的距离，即

两个函数可以在O（1）的时间内完成，主要的时间复杂度来源于两个循环的嵌套，设总的点数为n总的计算次数

根据上式，我们可以得出朴素做法求解二维最近点问题的时间复杂度是级别的。

1.2 二维最近点对分治做法

（1）算法描述

从分治的思想去考虑, 原问题可转化为求[1,mid]和[mid+1,r]的最近点对。但是可能存在一个最近点对, 它的一个端点在[1,mid]，另一个端点在[mid+1,r]。所以,我们在分治的时候还需要对这种情况进行检验。我们先对点集按x坐标升序排序,当我们求得左右区间的最近点对距离d1和d2后 d=min(d1,d2)，在[1,r]中找到跟中间点point[mid]的x距离小于d的点集P3，这样我们得到了候选点集P3。

实际上，我们得到的P3是一个以x=point[mid]。x为中轴线，长为2d, 宽为d的长方形，P3中的点集具有稀疏的特点(这一点我们稍后会用鸽巢原理证明)，我们对P3点集按y坐标排序,可以在常数级别的时间内做到对点集进行检验，得到当前的最近点对距离[6-8]。

（2）分治法的实现

基于以上的分析，我们得到二维最近点对分治做法的算法流程图如图2所示：

图2 分治法求二维最近点对流程图

（3）算法复杂度分析

由图2可以看出，这个算法在“对点集按坐标排序，并检验每个点后面坐标距离不超过的点”这一步的时候涉及到两层循环的嵌套，无法直观分析出时间复杂度的级别，下面将对复杂度进行证明：

如图3所示, 假设当前得到的最近点对距离为d,我们在某一递归过程中出现最近点对的两个端点分别处于不同区域, 即一个端点属于[1,mid]，另一个属于[mid+1,r]，那么我们沿着中线mid画出一个长2d, 宽d的小矩形区域, 对于这个矩形区域，很直观地看出它由两个边长为d的正方形组成。显然我们可以利用反证法和鸽巢原理证明小正方形中最多不会超过四个点[9-13]。

图3 2d * d 的小矩形

这与d是当前的最近点对事实矛盾, 因此这个正方形区域的点不超过四个。

同理, 对于右边的小正方形, 最多也只有四个点。那么总的矩形区域包含的点最多不会超过八个点。因此,我们在上述的二重循环中最多只会检验每个点之后的七个点,那么这个操作可以看做是在常数时间内完成的。于是,该算法的分割步骤和合并步骤总共耗时是O（n）的,x排序的耗时是O(nlogn), 而y对排序耗时为常数级别。

根据我们的分析, 算法耗费时间T（n）满足递归方程

因此，我们上文提到的分治法求解二维最近点对问题的总体时间复杂度级别是O(nlogn)。

1.3 三维最近点对的朴素做法

（1）算法描述

当二维最近点对问题扩展到三维时，朴素做法的思路并没有改变，此时只需改变函数的计算方式即可。

（2）时间复杂度分析

在复杂度方面，二维的朴素做法和三维的朴素做法区别在于函数，下面列出了函数在二维、三维下的形式：

显然两者在时间花费上都是O（1）的，那么时间复杂度方面和二维最近点对是一致的，都是O（n2）。

2 基于分治法的三维最近点对算法

2.1 三维最近点对O（n(logn)2）做法

二维空间下的最近点对问题能够通过分治法改进优化，我们能否将这个算法推广到三维的情况呢?还是那个思路, 在求1到n的最近点对问题,可以转化为求[1,mid]到[mid+1,r]的最近点对。

（1）算法描述

我们先对点按x坐标排序, 此时可以截取一个平面x=mid，对于平面的左右部分分治, 找到左右两端点集中最近距离d, 此时同样有几率会出现最近点对在分界面两边的情况, 比较难处理的是合并部分。 设左平面为P1,右平面为P2, 此时我们考虑做对点集按y坐标进行排序，并进行第二次分治——对y坐标进行分治。

第二次分治的时候，找到左右区间的最小值di, 并更新当前最小值d，此时已经转换成平面内的最近点对问题，我们对点集进行z坐标排序后对每个点进行检验，不断更新答案。

理论分析上，x,y,z坐标的地位是一致的，但是在实际情况中，由于数据的随机性，并不一定是按x分治, 再按y坐标分治最优，可以根据实际情况调换分治策略，找范围最小的一维作x分治[14,15]。

（2）算法的实现

基于上文的分析，我们可以给出两次分治求解三维最近点对的算法流程图如图4所示。

图4 两次分治的流程图

（3） 算法复杂度分析

对于x坐标进行分治的时候每个点在至多在logn个区间内被纳入tmp，所以他至多参与logn次对y坐标的分治，而对y坐标的分治实际上就是二维下的平面最近点对问题，时间复杂度为O(nlogn)，所以总复杂度是O（n(logn)2）。

2.2 三维最近点对分治做法

（1） 算法描述

我们考虑位于平面x=mid左右两端的点， 找出左端距离平面小于d的点加入到点集P1, 找出右端距离平面小于d的点加入到点集P2,那么点集P1到P2的任意两点的距离都需要我们去验证是否为最近点对。

对P1'的每一个点, 将它投影到x=mid平面,都可以对它建立一个d*2d*2d的长方体, 所有可选方案都将包含在长方体中, 如图5所示。

图5 以映射点展开的d * 2d * 2d 的长方体

可以通过鸽巢原理证明, 最多不超过24个点存在于这个长方体中。那么我们先对P1'和P2'的点进行y为第一关键字,z为第二关键字的排序。由于点集的y值具有上升的特点，可以通过双指针的方法维护一个满足条件的y坐标区间，在常数时间内完成检测[16]。

（2）算法实现

基于上文的分析，我们可以给出求解三维最近点对的O(nlogn)算法流程图如图6所示。

图6 O(nlogn)算法流程图

（3） 复杂度证明

如果一个小长方体里面有两个点，它们最远的距离是对角线的距离

这与d是最近点对距离的事实矛盾, 因此大长方体里最多24个点。

根据我们的分析, 算法耗费时间T(n)满足递归方程

与我们上文分析的分治法求解二维最近点对问题相似，它的总体时间复杂度级别是O(nlogn)。

3 性能测试

通过在随机生成的数据下考查算法的时间效率，并采用的在线判题系统的评测机作为速度评判标准，测试结果如表1所示。

表1 测试结果

我们可以对上述结果进行拟合，画出图像进行预测，如图7所示。

图7 拟合图像

在实际的测试中，我们的算法实际表现的时间复杂度与理论分析差别不大，分别属于O（nlogn）和O（n(logn)2）级别。

4 结论

本论文通过对二维最近点对问题的分析，引入了三维空间下的最近点对问题，推广并提出了两种利用分治法求三维最近点对问题的高效算法。在现今大数据和高性能计算领域里，对算法的时间复杂度提出了更高的要求，论文中提出的优化在实际计算中能够大大提升解决问题的效率。