查找曼哈頓距離中兩組之間的距離

Question

我正在從算法中學習測試，發現幾天內無法處理的問題。所以我寫在這裏尋求幫助。

有關平面給定兩個不相交的集合：

G={(x_1^G, y_1^G), (x_2^G, y_2^G), ..., (x_n^G, y_n^G)} 
D={(x_1^D, y_1^D), (x_2^D, y_2^D), ..., (x_n^D, y_n^D)} 

Where for every 1 <= i, j <= n we have y_i^D < y_j^G, so G is above D. 

查找 counts the distance between them 定義爲一種有效的算法：

d(G,D) = min{ d(a,b): a \in G and b\in D }, 
where d(a,b) = |x_a - x_b| + |y_a - y_b| 

爲O（n^2）是微不足道的，所以這不是答案。

我希望解決方案不是太難，因爲它是從測試前的材料審查。任何人都可以幫忙嗎？

我認爲這將是一個常見問題的特例。但是，如果是特殊情況，那麼解決方案可能會更容易？

Answer 1

有幾種不同的方法可以在O（n log n）時間內做到這一點。一，計算G點的曼哈頓距離Voronoi diagram，並據此建立點位置數據結構。這需要O（n log n）時間。對於每個D點，使用點位置數據結構查找最近的G點。這需要每D點O（log n）時間。取剛剛找到的對之間的距離的最小值，這就是你的答案。

二：你可以修改Fortune's algorithm這個問題;只爲D和G點保留單獨的二叉樹。那種煩人的描述。

下一個想法計算無窮範數最接近的對的距離，即max（| x1-x2 |，| y1-y2 |）。你可以將你的問題傾斜45度（用u = x-y，v = x + y代替），將它變成適當的形式。

三種（兩種變體）：按y座標排列所有點。保持d，迄今爲止所看到的最近一對之間的距離。我們將從上到下掃描一行，維護兩個二叉搜索樹，一個G點和一個D點。當一個點在掃掠線上方或上方時，我們將其從二叉搜索樹中移除。當掃描線首先遇到一個點時，比如一個D點，我們（1）檢查G二叉搜索樹，看看它是否有任何元素的x座標在新點的d內，根據需要更新d，和（2）將新點插入到D的二叉搜索樹中。每個點只會導致二進制搜索樹操作的數量不變，另外還有額外的工作量，因此掃描爲O（n log n）。這一點也不令人驚訝，所以我們的總體時間複雜度是所需的。

基於與三個類似的想法，你也可以制定一個分而治之的策略。