給定n個點（xi，yi）（1≤i≤n），要求找出其中距離最近的兩個點。
例14-7 假設在一片金屬上鑽n個大小一樣的洞，如果洞太近，金屬可能會斷。若知道任意兩個洞的最小距離，可估計金屬斷裂的概率。這種最小距離問題實際上也就是距離最近的點對問題。
通過檢查所有的n(n- 1 ) / 2對點，並計算每一對點的距離，可以找出距離最近的一對點。這種方法所需要的時間為(n2 )。我們稱這種方法為直接方法。圖1 4 - 1 3中給出了分而治之求解算法的偽代碼。該算法對於小的問題采用直接方法求解，而對於大的問題則首先把它劃分為兩個較小的問題，其中一個問題（稱為A）的大小為「n /2ù，另一個問題（稱為B）的大小為「n /2ù。初始時，最近的點對可能屬於如下三種情形之一： 1) 兩點都在A中（即最近的點對落在A中）；2) 兩點都在B中；3) 一點在A，一點在B。假定根據這三種情況來確定最近點對，則最近點對是所有三種情況中距離最小的一對點。在第一種情況下可對A進行遞歸求解，而在第二種情況下可對B進行遞歸求解。
if (n較小) {用直接法尋找最近點對
R e t u r n ; }
// n較大
將點集分成大致相等的兩個部分A和B
確定A和B中的最近點對
確定一點在A中、另一點在B中的最近點對
從上面得到的三對點中，找出距離最小的一對點
圖14-13 尋找最近的點對
為了確定第三種情況下的最近點對，需要采用一種不同的方法。這種方法取決於點集是如何被劃分成A、B的。一個合理的劃分方法是從xi（中間值）處劃一條垂線，線左邊的點屬於A，線右邊的點屬於B。位於垂線上的點可在A和B之間分配，以便滿足A、B的大小。
例2-8 考察圖14-14a 中從a到n的1 4個點。這些點標繪在圖14-14b 中。中點xi = 1，垂線x = 1如圖14-14b 中的虛線所示。虛線左邊的點(如b, c, h, n, i)屬於A，右邊的點(如a, e, f, j, k, l) 屬於B。d, g, m 落在垂線上，可將其中兩個加入A, 另一個加入B，以便A、B中包含相同的點數。假設d ,m加入A，g加入B。
設是i的最近點對和B的最近點對中距離較小的一對點。若第三種情況下的最近點對比小。則每一個點距垂線的距離必小於，這樣，就可以淘汰那些距垂線距離≥的點。圖1 4 - 1 5中的虛線是分割線。陰影部分以分割線為中線，寬為2 。邊界線及其以外的點均被淘汰掉，只有陰影中的點被保留下來，以便確定是否存在第三類點對（對應於第三種情況）其距離小於。用RA、RB 分別表示A和B中剩下的點。如果存在點對(p,q)，p?A, q?B且p, q的距離小於，則p?RA，q?RB。可以通過每次檢查RA 中一個點來尋找這樣的點對。假設考察RA 中的p 點，p的y 坐標為p.y，那麼只需檢查RB 中滿足p.y- ＜q.y＜p.y+的q 點，看是否存在與p 間距小於的點。在圖14-16a 中給出了包含這種q 點的RB的范圍。因此，只需將RB 中位於×2 陰影內的點逐個與p 配對，以判斷p 是否是距離小於的第三類點。這個×2 區域被稱為是p的比較區（comparing region）。
例2-9 考察例2 - 8中的1 4個點。A中的最近點對為(b,h)，其距離約為0 . 3 1 6。B中最近點對為(f, j)，其距離為0 . 3，因此= 0 . 3。當考察是否存在第三類點時，除d, g, i, l, m 以外的點均被淘汰，因為它們距分割線x= 1的距離≥ 。RA ={d, i, m}，RB= {g, l}，由於d 和m的比較區中沒有點，只需考察i即可。i的比較區中僅含點l。計算i 和l的距離，發現它小於，因此(i, l) 是最近的點對。
為了確定一個距離更小的第三類點，RA 中的每個點最多只需和RB 中的6個點比較，如圖1 4 - 1 6所示。
1. 選擇數據結構
為了實現圖1 4 - 1 3的分而治之算法，需要確定什麼是“小問題”以及如何表示點。由於集合中少於兩點時不存在最近點對，因此必須保證分解過程不會產生少於兩點的點集。如果將少於四點的點集做為“小問題”，就可以避免產生少於兩點的點集。
每個點可有三個參數：標號， x 坐標，y 坐標。假設標號為整數，每個點可用P o i n t l類（見程序1 4 - 8）來表示。為了便於按x 坐標對各個點排序，可重載操作符＜=。歸並排序程序如1 4 -3所示。
程序14-8 點類
class Point1 {
friend float dist(const Point1&, const Point1&);
friend void close(Point1 *, Point2 *, Point2 *, int, int, Point1&, Point1&, float&);
friend bool closest(Point1 *, int, Point1&, Point1&,float&);
friend void main();
p u b l i c :
int operator<=(Point1 a) const
{return (x <= a.x);}
p r i v a t e :
int ID; // 點的編號
float x, y; // 點坐標
} ;
class Point2 {
friend float dist(const Point2&, const Point2&);
friend void close(Point1 *, Point2 *, Point2 *, int, int, Point1&, Point1&, float&);
friend bool closest(Point1 *, int, Point1&, Point1&, float&);
friend void main();
p u b l i c :
int operator<=(Point2 a) const
{return (y <= a.y);}
p r i v a t e :
int p; // 數組X中相同點的索引
float x, y; // 點坐標
} ;
所輸入的n個點可以用數組X來表示。假設X中的點已按照x 坐標排序，在分割過程中如果當前考察的點是X [l :r]，那麼首先計算m= (l+r) / 2，X[ l:m]中的點屬於A，剩下的點屬於B。計算出A和B中的最近點對之後，還需要計算RA 和RB，然後確定是否存在更近的點對，其中一點屬於RA，另一點屬於RB。如果點已按y 坐標排序，那麼可以用一種很簡單的方式來測試圖1 4 - 1 6。按y 坐標排序的點保存在另一個使用類P o i n t 2 (見程序14-8)的數組中。注意到在P o i n t 2類中，為了便於y 坐標排序，已重載了操作符＜＝。成員p 用於指向X中的對應點。
確定了必要的數據結構之後，再來看看所要產生的代碼。首先定義一個模板函數d i s t (見程序1 4 - 9 )來計算點a, b 之間的距離。T可能是P o i n t 1或P o i n t 2，因此d i s t必須是P o i n t 1和P o i n t 2類的友元。
程序14-9 計算兩點距離
template
inline float dist(const T& u, const T& v)
{ / /計算點u 和v之間的距離
float dx = u.x-v. x ;
float dy = u.y-v. y ;
return sqrt(dx * dx + dy * dy);
}
如果點的數目少於兩個，則函數c l o s e s t (見程序1 4 - 1 0 )返回f a l s e，如果成功時函數返回t r u e。當函數成功時，在參數a 和b 中返回距離最近的兩個點，在參數d 中返回距離。代碼首先驗證至少存在兩點，然後使用M e rg e S o r t函數(見程序14-3) 按x 坐標對X中的點排序。接下來把這些點復制到數組Y中並按y 坐標進行排序。排序完成時，對任一個i，有Y [i ] . y≤Y [i+ 1 ] . y，並且Y [i ] .p給出了點i 在X中的位置。上述准備工作做完以後，調用函數close (見程序1 4 - 11 )，該函數實際求解最近點對。
程序14-10 預處理及調用c l o s e
bool closest(Point1 X[], int n, Point1& a, Point1& b, float& d)
{// 在n >= 2個點中尋找最近點對
// 如果少於2個點，則返回f a l s e
// 否則，在a 和b中返回距離最近的兩個點
if (n < 2) return false;
// 按x坐標排序
M e r g e S o r t ( X , n ) ;
// 創建一個按y坐標排序的點數組
Point2 *Y = new Point2 [n];
for (int i = 0; i < n; i++) {
// 將點i 從X 復制到Y
Y[i].p = i;
Y[i].x = X[i].x;
Y[i].y = X[i].y;
}
M e r g e S o r t ( Y,n); // 按y坐標排序
// 創建臨時數組
Point2 *Z = new Point2 [n];
// 尋找最近點對
c l o s e ( X , Y, Z , 0 , n - 1 , a , b , d ) ;
// 刪除數組並返回
delete [] Y;
delete [] Z;
return true;
}
程序1 4 - 11 計算最近點對
void close(Point1 X[], Point2 Y[], Point2 Z[], int l, int r, Point1& a, Point1& b, float& d)
{//X[l:r] 按x坐標排序
//Y[l:r] 按y坐標排序
if (r-l == 1) {// 兩個點
a = X[l];
b = X[r];
d = dist(X[l], X[r]);
r e t u r n ; }
if (r-l == 2) {// 三個點
// 計算所有點對之間的距離
float d1 = dist(X[l], X[l+1]);
float d2 = dist(X[l+1], X[r]);
float d3 = dist(X[l], X[r]);
// 尋找最近點對
if (d1 <= d2 && d1 <= d3) {
a = X[l];
b = X[l+1];
d = d1;
r e t u r n ; }
if (d2 <= d3) {a = X[l+1];
b = X[r];
d = d2;}
else {a = X[l];
b = X[r];
d = d3;}
r e t u r n ; }
/ /多於三個點，劃分為兩部分
int m = (l+r)/2; // X[l:m] 在A中，余下的在B中
// 在Z[l:m] 和Z [ m + 1 : r ]中創建按y排序的表
int f = l, // Z[l:m]的游標
g = m+1; // Z[m+1:r]的游標
for (int i = l; i <= r; i++)
if (Y[i].p > m) Z[g++] = Y[i];
else Z[f++] = Y[i];
// 對以上兩個部分進行求解
c l o s e ( X , Z , Y, l , m , a , b , d ) ;
float dr;
Point1 ar, br;
c l o s e ( X , Z , Y, m + 1 , r, a r, b r, d r ) ;
// (a,b) 是兩者中較近的點對
if (dr < d) {a = ar;
b = br;
d = dr;}
M e r g e ( Z , Y,l,m,r);// 重構Y
/ /距離小於d的點放入Z
int k = l; // Z的游標
for (i = l; i <= r; i++)
if (fabs(Y[m].x - Y[i].x) < d) Z[k++] = Y[i];
// 通過檢查Z [ l : k - 1 ]中的所有點對，尋找較近的點對
for (i = l; i < k; i++){
for (int j = i+1; j < k && Z[j].y - Z[i].y < d;
j + + ) {
float dp = dist(Z[i], Z[j]);
if (dp < d) {// 較近的點對
d = dp;
a = X[Z[i].p];
b = X[Z[j].p];}
}
}
}
函數c l o s e（見程序1 4 - 11）用來確定X[1:r] 中的最近點對。假定這些點按x 坐標排序。在Y [ 1 : r ]中對這些點按y 坐標排序。Z[ 1 : r ]用來存放中間結果。找到最近點對以後，將在a, b中返回最近點對，在d 中返回距離，數組Y被恢復為輸入狀態。函數並未修改數組X。
首先考察“小問題”，即少於四個點的點集。因為分割過程不會產生少於兩點的數組，因此只需要處理兩點和三點的情形。對於這兩種情形，可以嘗試所有的可能性。當點數超過三個時，通過計算m = ( 1 + r ) / 2把點集分為兩組A和B，X [ 1 : m ]屬於A，X [ m + 1 : r ]屬於B。通過從左至右掃描Y中的點以及確定哪些點屬於A，哪些點屬於B，可以創建分別與A組和B組對應的，按y 坐標排序的Z [ 1 : m ]和Z [ m + 1 : r ]。此時Y和Z的角色互相交換，依次執行兩個遞歸調用來獲取A和B中的最近點對。在兩次遞歸調用返回後，必須保證Z不發生改變，但對Y則無此要求。不過，僅Y [ l : r ]可能會發生改變。通過合並操作（見程序1 4 - 5）可以以Z [ 1 : r ]重構Y [ 1 : r ]。
為實現圖1 4 - 1 6的策略，首先掃描Y [ 1 : r ]，並收集距分割線小於的點，將這些點存放在Z [ 1 : k - 1 ]中。可按如下兩種方式來把RA中點p 與p的比較區內的所有點進行配對：1) 與RB 中y 坐標≥p.y的點配對；2) 與y 坐標≤p.y的點配對。這可以通過將每個點Z [ i ]（1≤i < k，不管該點是在RA
還是在RB中）與Z[j] 配對來實現，其中i＜j 且Z [ j ] . y - Z [ i ] . y＜ 。對每一個Z [ i ]，在2 × 區域內所檢查的點如圖1 4 - 1 7所示。由於在每個2 ×子區域內的點至少相距。因此每一個子區域中的點數不會超過四個，所以與Z [ i ]配對的點Z [ j ]最多有七個。
2. 復雜性分析
令t (n) 代表處理n個點時，函數close 所需要的時間。當n＜4時，t (n) 等於某個常數d。當n≥4時，需花費(n) 時間來完成以下工作：將點集劃分為兩個部分，兩次遞歸調用後重構Y，淘汰距分割線很遠的點，尋找更好的第三類點對。兩次遞歸調用需分別耗時t (「n /2ù」和t (?n /2?).
這個遞歸式與歸並排序的遞歸式完全一樣，其結果為t (n) = (nl o gn)。另外，函數c l o s e s t還需耗時(nl o gn)來完成如下額外工作：對X進行排序，創建Y和Z，對Y進行排序。因此分而治之最近點對求解算法的時間復雜性為(nl o gn)。
