林泽瀚

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

0 引言

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

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

1 相关工作

1.1 二维最近点对朴素做法

（1）算法描述

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

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

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

图1 朴素做法的伪代码

（3）时间复杂度分析

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

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

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

1.2 二维最近点对分治做法

（1）算法描述