最近點對演算法（closest pair of points）

給定地圖上 n 座城市的座標，哪兩座彼此最近？檢查每一對需要 O(n^2) 次距離計算，當大多數配對顯然相距甚遠時這很浪費。一個分治演算法以 O(n log n) 找出最近點對，方法是切分平面並對邊界處——那是遞迴唯一可能漏掉的配對所在——做巧妙處理。

把點依 x 座標排序，用一條垂直線切成左半 L 與右半 R。遞迴地找出 L 內最近點對（距離 dL）與 R 內最近點對（距離 dR）；令 d = min(dL, dR)。合併步驟必須抓出一個一點在 L、一點在 R 且比 d 更近的配對。關鍵的幾何洞見：任何這樣的配對都必須位於離分割線距離 d 之內，所以你只檢查線兩側寬度 2d 的垂直長條內的點。把那些長條內的點依 y 座標排序；接著有個了不起的事實成立——每個點只需與 y 序中後續常數個（至多 7 個）鄰居比較，因為一個 d 乘 2d 的區域內若超過這麼多點，必有其中兩點比 d 更近，與 d 是半內最小值矛盾。於是合併步驟是 O(n)，且 T(n) = 2 T(n/2) + O(n) = O(n log n)。

最近點對是計算幾何的里程碑：它展示分治法如何從一維自然延伸到二維，也是最乾淨的例子之一，說明一個幾何界（只需常數次長條比較）如何把合併步驟從二次的命運中拯救出來。同樣的長條與掃描想法在幾何中一再出現。常被提及的微妙細節是「常數次比較」這項主張：並非長條內點很少，而是它們之間的 d 間距如此緊密，使每個點在 y 排序中只能有少數幾個夠近的後繼。