C++中2點之間的最小距離

Question

我給出了m個位置（x，y座標）。我有n個請求找到離給定點P（x，y）最近的地方; （最小歐幾里德距離）

我該如何解決O（n * m）以下的問題，其中n是請求數和m個地點數？我可以使用平方歐幾里德距離，但它仍然是n * m。

Answer 1

試試kd-tree。一個高性能的庫實現可以在here找到。

注意：我指的是一個爲高維優化的近似最近鄰居搜索。這對您的應用程序可能有點矯枉過正。

編輯：

對於2D kd樹，建造時間將是O（M *日誌（M））和查詢時間爲O（N *的sqrt（M））。如果您的查詢次數超過log（m），這應該最終贏得天真的解決方案。

該庫意味着您不必執行它，因此複雜性不應該成爲問題。

如果您想推廣到高維度極快查詢，請查看locality sensitive hashing。

Answer 2

有趣。爲了減少n的影響，我想知道是否可能會幫助保存每個請求的結果，如遇到並處理它。一個聰明的結果表可能需要計算sqrt（x + y ）以解決後續請求。

Answer 3

Nearest-Neighbor-Problem，呃？我發現Robert Sedgewick Std Book在這些情況下非常有用。他也描述了Nearest Neighbour Search。