求点集中的最近点对有以下两种方法:
设p1=(x1, y1), p2=(x2, y2), …, pn=(xn, yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对。
1、蛮力法（适用于点的数目比较小的情况下）
1） 算法描述： 已知集合S中有n个点，一共可以组成n(n-1)/2对点对，蛮力法就是对这 n(n-1)/2 对点对逐对进行距离计算， 通过循环求得点集中的最近点对：
2）代码描述：
double MinDistance = double.maxvalue； //设置一个MinDistance存储最近点对的距离，初始值为无穷大
int PointIndex1,PointIndex2； //设置PointIndex1,PointIndex2分别存储最近点对的两个点编号
for (i=1; i< n; i++)
//循环计算
n(n-1)/2对点对的距离
{
for (j=i+1; j<=n; j++)
{
double PointDistance = Distance(S[i],S[j]); //求得point i和point j之间的距离
if PointDistance < MinDistance; //如果当前点对距离小于最小点对距离，则设置最小点对距离等于当前点对距离
{
MinDistance = PointDistance;
PointIndex1 = i;
PointIndex2 = j;
}
}
}
}
3）算法时间复杂度：算法一共要执行 n(n-1)/2次循环，因此算法复杂度为O(n
2
)
2、分治法
1）算法描述： 已知集合S中有n个点，分治法的思想就是将S进行拆分，分为2部分求最近点对。算法每次 选择一条垂线L，将S拆分左右两部分为SL和SR ，L一般取 点集S中所有点的中间点的x坐标来划分，这样可以保证SL和SR中的点数目各为n/2 ，
（否则以其他方式划分S，有 可能导致 S L 和S R 中点数目一个为1，一个为n-1，不利于算法效率，要尽量保持树的平衡性）
依次找出这两部分中的最小点对距离： δ L和 δ R，记 SL和SR 中最小点对距离 δ = min（ δ L， δ R），如图1：
以L为中心， δ为半径划分一个长带， 最小点对还有可能存在于 SL和SR的交界处 ， 如下图2左图中的虚线带，p点和q点分别位于 SL和SR 的虚线范围内，在这个范围内，p点和q点之间的距离才会小于δ，最小点对计算才有意义。
Figure 2
对于 S L虚框范围内的p点，在 SR 虚框中与p点距离小于δ的顶多只有六个点，就是图二右图中的2个正方形的6的顶点。这个可以反推证明，如果右边这2个正方形内有7个点与p点距离小于 δ ，例如q点，则q点与下面正方形的四个顶点距离小于 δ ，则和 δ 为 S L 和 S R 中 的最小点对距离相矛盾。因此对 于S L虚框中的p点 ，不需求出p点和右边虚线框内所有点距离，只需计算 S R中 与p点y坐标距离最近的6个点，就可以求出最近点对，节省了比较次数。
（否则的话， 最坏情形下， 在 S R 虚框中有可能会有n/2个点，对于 S L 虚框中的p点 ， 每次要比较 n/2 次，浪费了算法的效率 ）
代码描述：
1）对点集S的点x坐标和y坐标进行升序排序，获得点集Sx和Sy
2）令 δ =∞; // δ为最小点位距离
3）Divide_conquer（ Sx，Sy ， δ ） // 分治法
if （ Sx.count=1） then δ =∞; // 如果 Sx 中只有一个点，则 δ = ∞
return δ ;
else if （Sx.count=2 and d（ Sx.[0], Sx.[1]）< δ ） // 如果 Sx 中只有2个点，则 δ 为两点之间距离
δ = d（Sx.[0],）Sx.[1]）;
return δ ;
else // 如果 Sx 中多于2个点，则 将 Sx , Sy 分治，以中心点画线，将 Sx 分为左右两部分 SxL 和SxR，Sy 分为 SyL 和 S yR
j1=1, j2=1 , k1=1 , k2=1;
mid = Sx.count/2; // mid 为 Sx 中的中间点点号
L = Sx.[mid].x; // L 为 Sx 中的中间点x坐标
for(i=1,i< Sx.count ,i++)
{
if(i<= mid ) //将 Sx 中间线以左地方的点存入到 SxL ，新数组保持原来的升序性质
SxL[ k1 ] = Sx[i] k1++;
else //将 Sx 中间线以右的地方的点存入到 SxR ， 新 数组保持原来的升序性质
SxR.count[k2] = Sx[i] k2++;
if( Sy [i]. x <L) //将 Sy 中间线以左地方的点存入到 SyL ， 新 数组保持原来的升序性质
SyL[j1] = Sx[i] j1++;
else //将 Sy 中间线以右地方的点存入到 SyR ， 新 数组保持原来的升序性质
SyR[j2] = Sx[i] j2++;
}
δL = Divide_conquer（SxL，SyL ， δ） ; //获取 Sx 中的的最小点位距离 δL
δR = Divide_conquer（SxR，SyR ， δ） ; //获取 Sy 中的的最小点位距离 δR
δ = min ( δL , δR );
δ = merge( SyL，SyR ， δ); //获 Sx 中 Sy 交界处的最小点位距离，并综合 δL 和 δR 求出点集的最小点位距离 δ
return δ ;
函数merge(SyL，SyR ， δ)
merge(SyL，SyR ， δ)
{
i1=1,i2=1;
for(i=1,i< SyL .count,i++) //获取 SyL 中在左边虚框(距离小于 δ) 内的点 ，存入到 S' yL 中 ， 新 数组保持原来的升序性质
{
if( SyL [i].x>L- δ )
then S'yL[ i1 ]= SyL[i], i1++,
}
for(i=1,i<SyR.count,i++) //获取 SyR 中在右边虚框(距离小于 δ) 内的点 ，存入到 S' yR 中 ， 新 数组保持原来的升序性质
{
if( SyR [i].x<L+ δ )
then S'yR[ i2 ]= SyR[i], i2++,
}
t=1;
for (i=1,i<S'yL.count,i++)
{
while(S'yR[t].y< S'yL[t].yand t < SyR.count) //获取点集 S'yR 内距离点 S'yL[t] y坐标最接近的点号
{ t++; }
for( j= max(1,t-3), j<=min(t+3,S'yR.count),j++) //计算S'yR中的点与S'yL[t]y坐标相邻的六个点的距离
{
if(d(S'yL[ i ],S'yL[j])< δ ) //如果 前两点之间距离 小于 δ
then δ = d(S'yL[ i ],S'yL[j]); //则最小点位距离 δ 为当前两点之间距离
}
return δ
}
3）算法时间复杂度：
首先 对点集S的点x坐标和y坐标进行升序排序 ，需要循环2nlogn次，复杂度为 O(2nlogn )
接下来在分治过程中，对于每个S'yL中的点，都需要与S'yR中的6个点进行比较
O(n)= 2O(n/2) + (n/2)*6（一个点集划分为左右两个点集，时间复杂度为左右两个点集加上中间区域运算之和）
其解为O(n)< O(3nlogn )
因此总的时间复杂度为O(3nlogn ) ，比蛮力法的 O(n 2 ) 要高效。
分治法基础知识可参考http://blog.csdn.net/junerfsoft/archive/2008/09/25/2975495.aspx
改进算法可参考“求平面点集最近点对的一个改进算法”
