精选优质文档-倾情为你奉上三维空间的最接近点对问题刘志辉（中国民航大学 天津 ）摘要：最接近点对问题的求解就是在点集空间中求解最接近的一对点的距离。本文利用分治策略并结合预排序和分层映射技术把一维、二维情况下的最接近点对问题推广至三维，使问题在时间内得以解决，相对时间复杂度为的普通方法而言，效率得到很大的提高。关键词：最接近点对；鸽舍原理；分层映射；在文献1中，对一维和二维情况下的最接近点问题的求解进行了详细描述，于是引起了人们对三维情况下的最接近点对问题的关注。文献2中，提出了一种对三维最接近点对问题的求解方法：先对三维空间的点集进行两次预排序，利用与二维情况下相类似的合并算法，在时间内求出最接近的点对。但是其合并过程所采用的算法不明确，令人质疑。本文只需对空间点集进行一次预排序，然后在合并过程中采用分层映射技术使其在的时间内完成合并，从而整个算法的时间复杂度为，并且算法思路清晰。可以证明在渐近意义下，此算法已是最优算法。一、一维和二维情况下的最接近点对问题把一维情况下点集中的个点退化为轴上的个实数。于是最接近点对即为这个实数中相差最小
