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

三维空间的最接近点对问题 刘志辉 （中国民航大学 天津 300300） 摘要：最接近点对问题的求解就是在点集空间中求解最接近的一对点的距离。本文利用分治策略并结合预排序和分层映射技术把一维、二维情况下的最接近点对问题推广至三维，使问题在时间内得以解决，相对时间复杂度为的普通方法而言，效率得到很大的提高。 关键词：最接近点对；鸽舍原理；分层映射； 在文献[1]中，对一维和二维情况下的最接近点问题的求解进行了详细描述，于是引起了人们对三维情况下的最接近点对问题的关注。文献[2]中，提出了一种对三维最接近点对问题的求解方法：先对三维空间的点集进行两次预排序，利用与二维情况下相类似的合并算法，在时间内求出最接近的点对。但是其合并过程所采用的算法不明确，令人质疑。本文只需对空间点集进行一次预排序，然后在合并过程中采用分层映射技术使其在的时间内完成合并，从而整个算法的时间复杂度为，并且算法思路清晰。可以证明在渐近意义下，此算法已是最优算法。 一、一维和二维情况下的最接近点对问题 把一维情况下点集中的个点退化为轴上的个实数。于是最接近点对即为这个实数中相差最小的两个实数。显然可以先将这个实数排序好，映射到轴上，然后用轴上某个点将划分为大小大致相等的两个子集合和，且；，如图1所示。于是求中的最接近点对转变为分别求、中的最接近点对和其合并后的最接近点对。如果已求得和中的最小点对距离分别为和，合并时只需时间就能求得合并时的最接近点对，即和中分别离点最近的一个点，如图1中的点和。这样中的最接近点对的距离为。从而一维情况下只需用一次线性扫描就可以找出最接近点对，算法中主要计算时间花费在排序上，总的时间为。 图1 一维情况的最接近点对分治法 二维情况下的最接近点对可以表述为求平面中最接近的点对。先对平面中所有点按照坐标进行排序，用记排序后的点集，求出所有点坐标值的中位数，记为，然后用直线把点集划分为大致相等的两个子集和，且；。这样把求中的最接近点对转变为分别求、中的最接近点对和其合并后的最接近点对。子集中的最接近点对可以递归求得，但合并时最接近点对的求解比一维情况下要复杂些。设和分别为和中的最小距离，设。在合并时，对于中距离小于的两点和必定满足：和分别属于和，在此设，；令和分别表示距直线的左边和右边的宽为的两个区间，则，，如图2左所示。按照正常思维，中的所有点和中的所有点在最坏情况下有对最接近点对的候选者，但是和中的点具有稀疏性质，使得不必检查所有这个候选者，而最多只需要检查个候选者。和中的点的稀疏性表现在：对于中的任意一点，中与其构成最接近点对的候选者的点必定落在一个的矩形中，如图2左所示；利用鸽舍原理，中这样的候选点最多只有6个，如图2右所示，6个虚线矩形中每个矩形中最多只有一个候选点，具体描述可以参考文献[1]。因此，将和和中所有中点按其坐标排好序，则对中所有点最多只要检查中排好序的相继6个点。但此时合并的计算复杂度需要，并不是，没有达到预想的效果，不过可以通过在求解问题之前，把中的点按其坐标进行预排序来解决。所以二维情况下的最接近点对可以在的时间内求得。 图2二维情况的最接近点对分治法 二、最接近点对问题的三维推广 有了一维和二维的最接近点对描述，可以依此推广到三维。对于三维空间，所有的点有三个坐标。于是三维情况下的最接近点对可以表述为求空间中最接近的点对。 问题描述 先对三维空间中所有点按照坐标进行排序，用记排序后的点集。求出所有点坐标值的中位数，记为，然后用平面把点集划分为大致相等的两个子集和，且；。这样把求中的最接近点对转变为分别求、中的最接近点对和其合并后的最接近点对。然后依此方法递归地在和中求解最接近点对，设和分别为和中的最小距离，设。但求解合并时最接近点对比一维和二维都要复杂得多，成为问题求解的难点。 合并时，对于中距离小于的两点和必定满足：和分别属于和，在此设，。那么和距平面的距离均小于。因此，若令和分别表示距平面的左边和右边的宽为的两个长条形区间，则，，如图3左所示。此时，中的所有点和中的所有点在最坏情况下有对最接近点对的候选者。但是和中的点与二维情况下具有类同的稀疏性质，使得不必检查所有这个候选者。和中的点的稀疏性表现在：对于中的任意一点，中与其构成最接近点对的候选者的点必定落在一个的长方体中，如图3左所示；利用鸽舍原理，中这样的候选点最多只有24个[2]，如图3右所示，24个虚线小长方体中每个长方体中最多只有一个候选点。因为对于如图3右中，每一个小长方体中如果有2个以上中的点，设和是这样的2个点，则 因此，，这与前面的意义相矛盾。也就是说长方体中最多只有24个中的点，其实数字24并不重要，重要的是长方体中最多只有常数个这样的点。因此，在分治法的合并过程中，最多只需要检查个候选者，而不个候选者。在此并不能意味着