找到集合A中所有點最近鄰居集合B的算法

Question

假設我們有兩組點A，B，並且我們想爲集合A中的每個點找到集合B中的最近鄰居。

找到一個點的最近鄰點有很多好的算法。有什麼方法可以使用我們爲a_1獲得的信息來更有效地搜索a_2中的最近鄰居或集合中的其他點？

我在想這樣的事情：使用三角不等式來得到B中的每個點和新的a_2點之間可能的距離的間隔，然後對間隔的最大值和最小值進行排序，然後我只能搜索B中的點落在第一個區間。

Answer 1

1. 查找Voronoi diagram爲集合B點
2. 在集合A與B的Voronoi圖的點應用一個Sweep line algorithm只要掃線涵蓋了從集合A中的某個時刻，Voronoi圖這其中的邊緣之間看點位於。這允許確定該點屬於哪個Voronoi圖的面。其中給出了來自集合B的最近點。

步驟2的詳細信息：將Voronoi圖的所有邊與當前相交的掃描線保持在某個有序容器中。當掃描線覆蓋Voronoi圖的某個頂點時，從/到容器移除/添加入射到該頂點的邊。要查看某個點位於哪些邊之間，請在容器中獲取後繼/前導邊。

時間複雜度爲O（（M + N）log M）。 N = | A |，M = | B |。

Answer 2

您可能會從閱讀bentleys的「寫作高效程序」中獲益，因爲他在那裏處理旅行商推銷計劃的案例研究。他認識到的一個節約是兩點之間的距離涉及到一個昂貴的平方根。取平方根給出實際距離，不採用平方根給出一個可用於與其他相對值進行比較的數字。

我強烈推薦閱讀這本書。它會把你的大腦放在正確的地方。

Answer 3

蠻力解決方案可以使用集合B的最近點的樹狀圖。然後將集合A的每個點與樹狀圖進行比較。您也可以使用delaunay三角測量創建樹狀圖。