摘要訊息 : 使用高效的方法來尋找平面中距離最近的點.

0. 前言

在本文中, 我們將使用分而治之的思想來求解距離最近的點這個問題.

更新紀錄 :

• 2022 年 6 月 6 日進行第一次更新和修正.

1. 距離最近的點

給定二維平面上的 n 個點 (x_{1}, y_{1}), (x_{2}, y_{2}), ..., (x_{n}, y_{n}). 要求找到距離相近給定二維平面上的 n 個點 (x_{1}, y_{1}), (x_{2}, y_{2}), ..., (x_{n}, y_{n}). 要求找到距離相近的兩個點. 對於點 (x_{i}, y_{i}) 和 (x_{j}, y_{j}) 的距離定義為 \displaystyle {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} 滿足 \displaystyle {\mathop {\mathrm {card}}{\mathscr {A}} = \left \lceil \frac {n}{2} \right \rceil \text { 且 } \mathop {\mathrm {card}}{\mathscr {B}} = n - \left \lceil \frac {n}{2} \right \rceil \rfloor}. 接著, 點對的距離分為三種情況 :

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

對於前面兩種情況, 當 \mathop {\mathrm {card}}{\mathscr {A}} 和 \mathop {\mathrm {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) 表示點對 p 和 q 之間的距離. 為了尋找這樣的點對, 每次考察 \mathscr {R}_{\mathscr {A}} 中的一個點 p. 設 p 的 y 座標為 y_{p}. 然後, 我們只需在 \mathscr {R}_{\mathscr {B}} 中查看那些 y 座標與 y_{p} 相距小於 \delta 的點 q, 即 \left | y_{q} - y_{p} \right | < \delta. 否則, 根據距離公式, \left | y_{q} - y_{p} \right | \geq \delta, 那麼 d(p, q) \geq \delta. 因此, 若且唯若 q 滿足 \left | y_{q} - y_{p} \right | < \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), 則有 \displaystyle {T(n) = \begin {cases} \Theta(1) & {n < 4} \\ T \left ( \left \lceil \frac {n}{2} \right \rceil \right ) + T \left ( n - \left \lceil \frac {n}{2} \right \rceil \right ) + D(n) + C(n) & {n \geq 4}. \end {cases}} 從結果中取得最小距離的點對, 使用的時間為 \Theta(n), 因此 C(n) = \Theta(n). 對於點的一分為二, 即尋找一條中軸線, 所用的時間是常數級別的, 因此 D(n) = \Theta(1). 最終有 \displaystyle {T(n) = \begin {cases} \Theta(1) & {n < 4} \\ T \left ( \left \lceil \frac {n}{2} \right \rceil \right ) + T \left ( n - \left \lceil \frac {n}{2} \right \rceil \right ) + \Theta(n) & {n \geq 4}. \end {cases}} 若 \log_{2} {n} 為整數, 則 T(n) 有更簡單的遞迴方程式 \displaystyle {T(n) = \begin {cases} \Theta(1) & {n < 4} \\ T \left ( \frac {n}{2} \right ) + \Theta(n) & {n \geq 4}. \end {cases}} 解這個遞迴方程式, 可知 T(n) = \Theta(n\log {n}). 對於 n 不滿足 \log_{2}{n} 為整數的情形, 我們可以適當加入一些點來擴大 n, 使得n 滿足 \log_{2}{n} 為整數.