幫助解決二維最近的問題

Question

我知道我這樣做是錯誤的，但想不到正確的方法來解決這個問題。 我正在用下面列出的12點。 （1,2）（1,11）（7,8）（9,9）（12,13），（13,4），（20,8），（22,3），（23,12） ，（24,14），（26,7），（31,10）

我把這種成兩個子集

左=（1,2）（1,11）（7,8）（ 9,9）（12,13），（13,4）

Right =（20,8），（22,3），（23,12），（24,14），（26,7） ，（31,10）

此外削減

LLeft =（1,2）（1,11）（7,8）

RLeft =（9,9）（12,13），（13,4）

LRight =（20,8），（22,3），（23,12）

RRight =（24 ，14），（26,7），（31,10）

查找每組的最小距離。

LLeft（1,2）（1,11）爲9，（1,11）（7,8）爲6.7，（1,2）（7,8）是8.48

的min是6.7

RLeft（9,9）（12,3）是6.70，（9,9）（13,4）是6.4，（12,3）（13,4）是1.14

的分是1.14

LRight（20,8）（22,3）是5.38（20,8）（23,2）是5，（22,3）（23,12）是9.05

的分是5

RRight（24,14）（26,7）是7.28（24,14）（31,10）是8.06（26,7）（31,10）是5.83

的min是5.83

所以現在我有LLeft，RLeft，LRight和RRight。我需要找到的是LRLeft，RLLEft_Right（中間值）和LRRight。這是我感到困惑的地方。我能想到獲得LRLeft的唯一方法就是將LLeft和RLEft中的每一點都找出來，並找出兩者之間的距離。然後使用該距離並將其與LLeft和RLeft進行比較，這會給我左側兩點之間的最短距離。然後我在右邊和中間做同樣的事情。我很確定有一個更快，更好的方法來做到這一點，但我無法弄清楚。

Answer 1

你應該看看http://en.wikipedia.org/wiki/Closest_pair_of_points_problem#Planar_case

Here's a better resource for Step 4，而是讓你開始：在遞歸，如果我們已經有最小距離左，右集內的d1和d2分別接如果有一對距離更近的點 - 其中一個來自左側，另一個來自右側 - 然後我們只需要檢查分隔線的距離d內的點，其中d = min(d1,d2)。