1、最接近点对问题的定义

给定平面上面的n个点，找其中的一对点，使得在n个点组成的所有点对中，该点对间的距离最小。

2、最接近点的分析

事实上，最接近点的对数有可能是多余一对的，其实按照简单来说我们可以只找到其中的一对点来进行求解问题足矣。

其实只要将每一点和其他n-1个点的距离算出来,找出达到最小距离的两点即可。但是其实这个效率比较低下。 

3、改进思想

首先我们可以想到分治法相关求解问题的思想，我们可以将平面上面的n个点的集合S分成2个子集S1和S2，每个子集中大约有n/2个点。然后在每个子集中递归的求其最接近的点对。其实最关键的就是我们如何实现分治法中的合并问题，意思就是如何通过S1和S2中的最接近点对求得原集合中的最接近点对。要是最后我们所求的两个最接近点对都在集合中的话，那么问题很好解决。 

4、解决办法

其实我们可以把这个问题解决为x坐标轴上面的一维问题进行求解，假设使用x轴上面的某个点m将S集合划分成S1和S2。然后递归的在S1和S2上面找出最接近点对{p1,p2}和{q1,q2}，所以我们可以容易的知道S中的最接近点对或者是{p1,p2}或者是{q1,q2}。