給定二維平面上的 n 個點 (x_{1}, y_{1}), (x_{2}, y_{2}), ..., (x_{n}, y_{n}). 要求找到距離相近的兩個點. 其中, 對於點 (x_{i}, y_{i}), (x_{j}, y_{j}) 的距離為

d = \sqrt {(x_{i} - x_{j})^{2} + (y_{i} - y_{j})^{2}}, i, j = 1, 2, ..., n, i \neq j

最直接的方法是考察所有的點對組合, 分別計算其距離, 並且從中選出最小的. 當 n 比較小的時候, 這個方法最直接簡單, 但是當 很大的時候, 這個方法的複雜度就很高. 使用上述方法求解, 時間複雜度為 O(n^{2}). 但是, 如果使用分而治之的思想, 可以降低複雜度. 首先進行劃分, 對於 n 個點, 其必定分佈在某個矩形內, 選定一條中軸線將 n 個頂點劃分為 \mathscr {A}\mathscr {B} 兩個集合. 若有點剛好落在中軸線上, 那麼將這些點平均地分配到集合 \mathscr {A}\mathscr {B} 中. 不妨設 \mathscr {A}\mathscr {B} 滿足

card\mathscr {A} = \left \lceil \frac {n}{2} \right \rceil, card\mathscr {B} = \left \lfloor \frac {n}{2} \right \rfloor

接著, 點對的距離分為三種情況 :

  • 兩個點都落在 \mathscr {A}
  • 兩個點都落在 \mathscr {B}
  • 一個點落在 \mathscr {A} 中, 另一個點落在 \mathscr {B}

對於前面兩種情況, 當 card\mathscr {A}card\mathscr {B} 仍然較大的時候, 可以繼續分而治之, 直到 \mathscr {A}\mathscr {B} 較小的時候, 運用直接法求解. 對於第三種情況, 則要使用不同的方法進行求解 : 設 \mathscr {A} 中距離最短的點對的距離為 \xi, \mathscr {B} 中距離最短的點對距離為 \zeta, 記 \delta = \min \left \{ \xi, \zeta \right \}. 我們的目的是試圖從第三類點對中尋找一個點對, 使得其距離比 \delta 還要小. 首先, 與中軸線距離大於 \delta 的點需要被排除. 以中軸線為基礎, 寬度為 2\delta. 若存在點被保留下來, 那麼從這些點中確定是否存在一個點對, 使得距離小於 \delta

\mathscr {R}_{\mathscr {A}}\mathscr {R}_{\mathscr {B}} 分別表示 \mathscr {A}\mathscr {B} 中被保留下來的點的集合. 若存在一點對 (p, q), 使得 p \in \mathscr {A}, p \in \mathscr {B}, 且 d(p, q) < \delta, 則必有 p \in \mathscr {R}_{\mathscr {A}}, q \in \mathscr {R}_{\mathscr {B}}. 其中, d(p, q) 表示點對 pq 之間的距離. 為了尋找這樣的點對, 每次考察 \mathscr {R}_{\mathscr {A}} 中的一個點 p. 設 py 座標為 y_{p}. 然後, 我們只需在 \mathscr {R}_{\mathscr {B}} 中查看那些 y 座標與 y_{p} 相距小於 \delta 的點 q, 即 |y_{q} - y_{p|} < \delta. 否則, 根據距離公式, |y_{q} - y_{p}| \geq \delta, 那麼 d(p, q) \geq \delta. 因此, 若且唯若 q 滿足 |y_{q} - y_{p}| < \delta 時, 才可能與 p 構成間距小於 \delta 的點對. 最終, 我們將區域縮小到大小為 \delta \times 2\delta 的區域, 稱其為比較區. 對於確定的 p \in \mathscr {R}_{\mathscr {A}}, 只需要在比較區尋找一個 q \in \mathscr {R}_{\mathscr {B}} 即可

最後, 我們來分析使用了分而治之思想的解決方案的時間複雜度. 令 T(n) 表示使用了分而治之思想的演算法的運作時間, 當 n < 4 的時候, 我們採用直接法求解, 其用時為 \Theta(1), 則有

T(n) = \begin {cases} \Theta(1) & {n < 4} \\ T(\left \lceil \frac {n}{2} \right \rceil) + T(\left \lfloor \frac {n}{2} \right \rfloor) + D(n) + C(n) & {n \geq 4} \end {cases}

從結果中取得最小距離的點對, 使用的時間為 \Theta(n), 因此 C(n) = \Theta(n). 對於點的一分為二, 即尋找一條中軸線, 所用的時間是常數級別的, 因此 D(n) = \Theta(1). 最終有

T(n) = \begin {cases} \Theta(1) & {n < 4} \\ T(\left \lceil \frac {n}{2} \right \rceil) + T(\left \lfloor \frac {n}{2} \right \rfloor) + \Theta(n) & {n \geq 4} \end {cases}

若限定 \log_{2} {n} 為整數, 則 T(n) 有更簡單的遞迴方程式

T(n) = \begin {cases} \Theta(1) & {n < 4} \\ T(\frac {n}{2}) + \Theta(n) & {n \geq 4} \end {cases}

解這個遞迴方程式, 可知 T(n) = \Theta(n \log {n})