距离最近的两点（Closest Pairs of Points）是计算几何中的一个著名问题：给定一组平面坐标，找出该组坐标里面距离最近的两个点。如下图中所示，红色两点是所有坐标点中距离最近的一对。
该图片来自维基百科 – Closest pairs of points problem.
最简单直接的解决方法是暴力破解（Brutal Force），也就是计算所有两点之间的距离，然后找到最小值。但是这种方法需要的计算时间随着坐标位置的增加会呈指数级别增长，所以暴力破解方法的时间复杂度是 O(n2)。
一个更好的解决办法是采用分而治之算法（Divide and Conquer）。也就是先用二分法递归计算出各点之间的距离，然后逐一合并找出最小的那一个距离。这个算法的时间复杂度是 O(nlog2n) 。但是这里面有一个地方需要做特殊处理，我们一起来看看具体算法：
注：该图片来自网页 – Closest Pair: A Divide-and-Conquer Approach
算法思路：
- 把所有的点集合 S 分为大致数量相等的两部分 S1和 S2，S1 和 S2 以Y值 L 来分割，如上图所示。
- 使用二分递归算法计算出 S1 集合里面的最小两点距离 d1 和 S2 集合里面的最小两点距离 d2。
- 比较 d1 和 d2 得到两个集合之中的最小两点距离 d。
- 现在需要考虑的特殊情况是：如果S1集合中有一个点P1，和S2集合中的一个点P2之间的距离比 d 还要小，那么我们需要再做一次搜索。不过这次搜索的范围可以缩小到以Y值L为中心，两边距离Y小于或等于 d 的一个长条状范围里的点，如下图所示。
- 注：该图片来自网页 – Closest Pair: A Divide-and-Conquer Approach
- 位于上面条状范围里的任意一点P1，第二次搜索的范围缩小到满足下面两个条件的点P2：
- P1 和 P2 的 X值距离小于 d。
- P1 和 P2 的 Y值距离小于 d。
- 如上图的蓝色长边为 2d 宽边为 d的长方形中的坐标点，如果满足两两之间的距离不小于d的情况，最多只有六个点可以分布在其中。这个定理的证明可以参见文章： A rectangle of width d and height 2d can contain at most six points such that any two points are at distance at least d。
- 按照这个思路，我们需要做的处理如下：
- 把位于条状范围里的所有坐标点按照Y值由小到大排序，然后循环检查每一个坐标P。
- 对于当前坐标P，搜索离它最近的五个邻居坐标，找出距离最小的值。
- 全部坐标搜索完毕后，把找到的最小值和第一次递归搜索找到的d值做比较，取较小的一个，这就是我们要找的最小距离。
时间复杂度：
上述算法总共有六个步骤，每一个步骤的时间复杂度如下：
- 把坐标集合S分割为两组S1和S2，采用二分递归算法分别找出两组里面的最小距离 d1和d2。
- 从d1 和 d2 中找出较小的一个 d 值。 – O(1)
- 把坐标集合中离Y值L距离超过d的点删除。- O(n)
- 把剩余坐标按照Y值排序。- O(nlogn)
- 遍历剩余坐标，每一个点计算它和周边的五个点之间的距离。- O(n)
- 如果有比d小的值，就更新d值。- O(1)
上面算法步骤2到6是Divide and Conquer里面的合并（Conquer），因为Divide采用二分算法所以合并的运行次数是logn。从上面的分析可以看出，第2-6步的复杂度由第4步排序来决定，所以复杂度是 O(nlogn)。因为第1步二分递归算法里面，步骤2-6需要在每一个层级都重复一次，所以总的时间复杂度是：O(logn*nlogn) = O(nlog2n)
