摘要: 寻找平面内最近点对的问题是一个传统的计算几何的问题，它要求从平面点的集合中选取出距离最小的点对，该问题在很多方面都有应用，比如说交通控制系统等等。 最简单的方法就是蛮力法，也就是将所有的点对的距离给求出来，然后得到距离最小的点对，这样的时间开销是平方量级的。 Shamos 和 Hoey 在 1975 年提出了在 O(n lg n) 时间内寻找平面内最近点对的分治算法。算法首先将平面上的点均分为左右两部分，假设分割线为 l , 然后对各个部分递归的调用该算法，得到一个最小距离 c. 此时在归并的时候只要考虑 l 两边与 l 距离为 c 的带状区域内的点之间的最小距离。如果平面上有某对点之间的距离小于 c 的话那么这对点必定在这个带内，否则最小距离就是 c 。对带左半部分内的每个点，算法需要考虑带右半部分内的至多 6 个点，假设平面上点的个数为 n , 该算法在归并时最坏情况下需要求出 3n 对点对之间的距离，从而整个算法计算距离的复杂度为 3n lg n 。但是距离的计算量相对于其他基本代数或者逻辑操作来说开销比较大 , 所以如何降低整个算法过程中距离的计算次数成为我们考虑的重点，我们改进的目标就是使得计算距离的复杂度尽可能的小。 在 1998 年，周玉林等人对 SH 算法进行了改进。他们证明了对带左半部分中的每个点 v ，可以在带右半部分中画出两个 c*c 的正方形区域，两个正方形的左边均与直线 l 重合，其中一个正方形的底边所在直线经过 v 点，而另一个的顶边所在直线经过 v 点。这样，在归并中只要考察上下两个正方形中与点 v 的 y 坐标值最接近的各两个点，计算这四个点与点 v 的距离就可以了。在最坏情况下，归并只需求出 2n 对点对之间的距离。 本文在此基础上做了进一步改进，我们证明了对每一个点 v , 只需要考虑上面所提到的四个点中的三个即可，即把这四个点中 x 轴坐标值与点 v 的 x 轴坐标值差的绝对值最大的那个点去掉。 我们证明了， 对于每一个在带左半部分的点 v , 如果存在以上提到的四个点， 并且如果这四个点和点 v 的最小距离比 c 小， 那么与点 v 的距离最小的点就不可能是算法中去掉的点，也就是说这个与点 v 距离最小的点必定在留下来的三个点中。这样，在归并时 , 最坏情况只需要计算 3n/2 对点对之间的距离，从而使整个算法计算距离的复杂度降为 (3n lg n)/2, 这个值为最初 SH 算法的一半。