黑盒子部落格~電腦不難~資訊一把抓~

Closest Pair

一群點當中，距離最近的兩個點叫作「最近點對」。

演算法（ Enumeration ）

窮舉法的時間複雜度是 O(N^2) ，可以找出所有的最近點對。

實作時，減少 sqrt 函式的呼叫次數，盡量紀錄距離的平方，可以減少計算時間。

演算法（ Sweep Line ）

預先按照水平座標排序，再以水平距離裁減搜尋範圍。

一、先排序所有點，以X座標為主，Y座標無所謂。
二、從左往右掃，依序窮舉各點作為左端點。
　甲、從左端點開始往右掃，依序窮舉各點作為右端點。
　乙、若左右兩點距離差太遠、超過目前發現的最近點對距離，
　　　就可以停止窮舉右端點。

也可以先窮舉右端點、再窮舉左端點。下個段落會用到。

最差情況是所有點都在同一條垂直線上，將會窮舉到所有點對，完全無法裁減搜尋範圍。儘管時間複雜度仍是 O(N^2) ，但是實際效率極佳。

實作時，避免直接排序原資料，複製一份指標或索引值來排序，可以減少計算時間。

UVa 10245 10750 11378 ICPC 6666

演算法（ Sweep Line ）

要避免最差情況，有個想法是：再將所有點依照垂直方向排序。如此一來，時間複雜度得降低為 O(NlogN) 。

一、位於右端點左方、距離 d 以下的點，才有可能形成最近點對。也就是以右端點為圓心、左半圓涵蓋的點（包含邊界）。照理來說，我們只需要檢查半圓範圍裡面的點。

運用左掃描線作為輔助，跟隨右掃描線亦步亦趨，我們得以輕易的過濾出水平距離 d 以下的點，但是無法進一步過濾出半徑距離 d 以下的點。

折衷的方式是依照 Y 座標排序水平距離 d 以下的點，然後運用二分搜尋法找到右端點，然後找到 Y 座標比右端點稍大、稍小的點──這些點很可能就在半圓之內。

二、右端點左方的點，兩兩之間的距離，至少是 d 。

點與點之間無法太過密集擁擠，能夠組成最近點對的左端點並不多。其實只需檢查右端點的前兩點、後兩點，作為左端點，就能囊括所有最近點對！

最極端的情況，是以右端點為中心、左半正方形涵蓋的點（包含邊界）。

由於右掃描線不斷往右移動，水平距離 d 以下的點必須不斷重新排序，很花時間。運用 Binary Tree 資料結構，即可隨時保持排序，節省時間。

一、預先排序所有點，X座標為主，Y座標為輔。
二、建立一棵平衡二元樹（AVL Tree），
　　儲存右端點的左方、水平距離小於等於d的點。
　　二元樹排序以Y座標為主，X座標為輔。一開始是空的。
　　d是當下的最近點對距離。一開始是無限大。
三、右掃描線依序窮舉各點作為右端點。
　甲、二元樹刪除與右端點水平距離大於d的點們。
　　　（左掃描線視情況往右移動。）
　乙、二元樹加入右端點。
　丙、二元樹尋找右端點的前兩點與後兩點，嘗試更新最近點對。

掃描線輔以資料結構，是計算幾何的經典手法，請讀者牢記在心。

時間複雜度。排序 O(NlogN) 。掃描線 O(N) 。二元樹總共刪除 N 個點、加入 N 個點、尋找 5N 個點， O(NlogN) 。

【待補程式碼】

演算法（ Divide and Conquer ）

時間複雜度是 O(N * (logN)^2) ，可以找出所有的最近點對。原理是把平面切割成左右兩側，答案分為「最近點對在左側」、「最近點對在右側」、「最近點對橫跨兩側」等三種情形。先將左側與右側分別遞迴求解之後，再利用左側與右側的答案，快速的算出橫跨兩側的答案。

Preprocessing:
一、排序所有點，以X座標為主，Y座標無所謂。O(NlogN)
二、檢查是否有共點。如果有，就找出所有共點，演算法結束。O(N)

Divide：
把所有點分為左右兩側，左側、右側的點數盡量一樣多。

Conquer：
左側、右側分別遞迴求解。

Combine：
一、利用左側、右側的最佳解d，求出橫跨兩側的解：
　甲、首先找出靠近中線的點，水平距離小於d、包含d。O(N)
　　　（小於d、不包含d，則只找出其中一組最近點對。）
　乙、排序這些點，Y座標為主，X座標為輔。O(NlogN)
　丙、每一個點都找其上方鄰近的點，看看能不能形成最近點對。
　　　只需檢查至後三點。O(N*3) = O(N)
二、答案為左側、右側、橫跨兩側，三者當中的最佳解。

以下提供釋例。畫面上有一些點。

把點分為左側與右側，點數盡量一樣多。左側與右側的交界處可能會銜接，也可能不會銜接。左右兩側通常是不一樣寬的。

左側、右側分別遞迴求解，最後求得這兩種情況下的最近點對。最近點對的距離為 d 。

左側的每一個點，半徑 d 以內的範圍（不包含邊界），不會有其他左側的點存在，只可能出現另一側的點。右側亦如是。

要找出橫跨兩側的點對，可以從左側的右邊線，往左距離 d 以內的範圍裡（包含邊界）的這些點，有可能與右側的點形成最近點對。

也可以以右側的左邊線為主。

從左側的右邊線，往右距離 d 以內的範圍裡的這些點，則是可能的另一頭端點的範圍。

要找出橫跨兩側的最近點對，只要依序窮舉左側右邊界距離 d 以內、位於左側的點，作為左端點；再找左側右邊界距離 d 以內、位於右側的點，作為右端點。

從這裡開始衍生兩種實作方式：

一、最容易理解的方式，是從下往上掃描左端點；針對每個左端點，找到合適的右端點。右側之中，點與點之間的距離至少是 d 。運用先前的分析手法，我們只需檢查掃描線的中下兩點、上兩點，作為右端點，就能囊括所有橫跨兩側的最近點對。

此處省略分析過程，讀者可以自行畫圖觀察。

實作時，運用右側掃描線作為輔助，跟隨左側掃描線亦步亦趨，就能快速找到中下兩點、上兩點，而不必使用二分搜尋法。

二、另一個難以理解、但是容易實作的方式，是把範圍內的這些點全部混在一起，不分左右，然後從下往上掃描。先窮舉下端點，再尋找上方鄰近的點作為上端點，檢查是否形成最近點對。

最多只需要檢查下端點的後四點，就一定囊括所有橫跨兩側的最近點對。

此處省略分析過程，讀者可以自行畫圖觀察。蠻複雜的喔！可以先將左側、右側的分布情形分開畫好，再將左右兩側拼在一起。

更進一步。第四點一定與同側的另外一點形成最近點對，之後還是能檢查到，所以不必檢查第四點、只需要檢查後三點。

以上圖例都是掃描線掃中左側的點，讀者可以自行分析掃描線掃中右側的點的所有情況。大功告成。

教科書通常只談到後五點；此處更加深入分析，從後五點逼近至後三點。儘管推理過程讓人感覺似乎很有學問，但是執行速度仍舊不如窮舉法。這種鑽牛角尖又不切實際的學問，不如不學。

如果在 Combine 階段，以 Merge Sort 將所有點重新依照 Y 座標排序，時間複雜度可以降到 O(NlogN) 。然而執行 Merge Sort 的額外負擔實在太大，通常會比原來的方法慢上許多。

如果一開始將所有點複製一份，先以 Y 座標排序，那麼在遞迴途中就不用每次都排序。如此會使時間複雜度暴增為 O(N^2) ，甚至比窮舉法還慢。