求點集中的最近點對有以下兩種方法:

設(shè)p1=(x1, y1), p2=(x2, y2), …, pn=(xn, yn)是平面上n個點構(gòu)成的集合S，設(shè)計算法找出集合S中距離最近的點對。

1、蠻力法（適用于點的數(shù)目比較小的情況下）

1） 算法描述： 已知集合S中有n個點，一共可以組成n(n-1)/2對點對，蠻力法就是對這 n(n-1)/2 對點對逐對進(jìn)行距離計算， 通過循環(huán)求得點集中的最近點對：

2）代碼描述：

double MinDistance = double.maxvalue； //設(shè)置一個MinDistance存儲最近點對的距離，初始值為無窮大

int PointIndex1,PointIndex2； //設(shè)置PointIndex1,PointIndex2分別存儲最近點對的兩個點編號

for (i=1; i< n; i++) //循環(huán)計算 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; //如果當(dāng)前點對距離小于最小點對距離，則設(shè)置最小點對距離等于當(dāng)前點對距離

{

MinDistance = PointDistance;

PointIndex1 = i;

PointIndex2 = j;

}

}

}

}
3）算法時間復(fù)雜度：算法一共要執(zhí)行 n(n-1)/2次循環(huán)，因此算法復(fù)雜度為O(n ² )

2、分治法

1）算法描述： 已知集合S中有n個點，分治法的思想就是將S進(jìn)行拆分，分為2部分求最近點對。算法每次 選擇一條垂線L，將S拆分左右兩部分為SL和SR ，L一般取 點集S中所有點的中間點的x坐標(biāo)來劃分，這樣可以保證SL和SR中的點數(shù)目各為n/2 ，

（否則以其他方式劃分S，有 可能導(dǎo)致 S L 和S R 中點數(shù)目一個為1，一個為n-1，不利于算法效率，要盡量保持樹的平衡性）

依次找出這兩部分中的最小點對距離： δ L和 δ R，記 SL和SR 中最小點對距離 δ = min（ δ L， δ R），如圖1：

以L為中心， δ為半徑劃分一個長帶， 最小點對還有可能存在于 SL和SR的交界處 ， 如下圖2左圖中的虛線帶，p點和q點分別位于 SL和SR 的虛線范圍內(nèi)，在這個范圍內(nèi)，p點和q點之間的距離才會小于δ，最小點對計算才有意義。

Figure 2

對于 S L虛框范圍內(nèi)的p點，在 SR 虛框中與p點距離小于δ的頂多只有六個點，就是圖二右圖中的2個正方形的6的頂點。這個可以反推證明，如果右邊這2個正方形內(nèi)有7個點與p點距離小于 δ ，例如q點，則q點與下面正方形的四個頂點距離小于 δ ，則和 δ 為 S L 和 S R 中 的最小點對距離相矛盾。因此對 于S L虛框中的p點 ，不需求出p點和右邊虛線框內(nèi)所有點距離，只需計算 S R中 與p點y坐標(biāo)距離最近的6個點，就可以求出最近點對，節(jié)省了比較次數(shù)。

（否則的話， 最壞情形下， 在 S R 虛框中有可能會有n/2個點，對于 S L 虛框中的p點 ， 每次要比較 n/2 次，浪費了算法的效率 ）

代碼描述：

1）對點集S的點x坐標(biāo)和y坐標(biāo)進(jìn)行升序排序，獲得點集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坐標(biāo)

for(i=1,i< Sx.count ,i++)

{

if(i<= mid ) //將 Sx 中間線以左地方的點存入到 SxL ，新數(shù)組保持原來的升序性質(zhì)

SxL[ k1 ] = Sx[i] k1++;

else //將 Sx 中間線以右的地方的點存入到 SxR ， 新 數(shù)組保持原來的升序性質(zhì)

SxR.count[k2] = Sx[i] k2++;

if( Sy [i]. x <L) //將 Sy 中間線以左地方的點存入到 SyL ， 新 數(shù)組保持原來的升序性質(zhì)

SyL[j1] = Sx[i] j1++;

else //將 Sy 中間線以右地方的點存入到 SyR ， 新 數(shù)組保持原來的升序性質(zhì)

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 δ ;

函數(shù)merge(SyL，SyR ， δ)

merge(SyL，SyR ， δ)

{

i1=1,i2=1;

for(i=1,i< SyL .count,i++) //獲取 SyL 中在左邊虛框(距離小于 δ) 內(nèi)的點 ，存入到 S' yL 中 ， 新 數(shù)組保持原來的升序性質(zhì)

{

if( SyL [i].x>L- δ )

then S'yL[ i1 ]= SyL[i], i1++,

}

for(i=1,i<SyR.count,i++) //獲取 SyR 中在右邊虛框(距離小于 δ) 內(nèi)的點 ，存入到 S' yR 中 ， 新 數(shù)組保持原來的升序性質(zhì)

{

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 內(nèi)距離點 S'yL[t] y坐標(biāo)最接近的點號

{ t++; }

for( j= max(1,t-3), j<=min(t+3,S'yR.count),j++) //計算S'yR中的點與S'yL[t]y坐標(biāo)相鄰的六個點的距離

{

if(d(S'yL[ i ],S'yL[j])< δ ) //如果 前兩點之間距離 小于 δ

then δ = d(S'yL[ i ],S'yL[j]); //則最小點位距離 δ 為當(dāng)前兩點之間距離

}

return δ

}

3）算法時間復(fù)雜度：

首先 對點集S的點x坐標(biāo)和y坐標(biāo)進(jìn)行升序排序 ，需要循環(huán)2nlogn次，復(fù)雜度為 O(2nlogn )

接下來在分治過程中，對于每個S'yL中的點，都需要與S'yR中的6個點進(jìn)行比較

O(n)= 2O(n/2) + (n/2)*6（一個點集劃分為左右兩個點集，時間復(fù)雜度為左右兩個點集加上中間區(qū)域運算之和）

其解為O(n)< O(3nlogn )

因此總的時間復(fù)雜度為O(3nlogn ) ，比蠻力法的 O(n ² ) 要高效。

分治法基礎(chǔ)知識可參考http://blog.csdn.net/junerfsoft/archive/2008/09/25/2975495.aspx

改進(jìn)算法可參考“求平面點集最近點對的一個改進(jìn)算法”

平面最近點對