2維空間中的最短路徑和排序點

Question

假設我在2維空間中有一個對象，並且需要該對象訪問的一組點。點可以在任何時候添加，但不能刪除。

我想要的是能夠確定下一個最近的點到我的對象是O（LG電子（n））的時間，然後去給它，然後確定下一個最接近的，等等。

一個簡單的優先級隊列不適用於此，因爲對象正在改變位置，所以隊列每次移動時都需要重新排列。我想象的是將點排列成BST，但我不確定如何對（x，y）進行排序，或者甚至可能。

這感覺就像我可以試圖解決traveling salesman沒有意識到，如果是這樣，我道歉哈哈。

Answer 1

一種選擇是使用像四叉樹或k-d樹這樣的空間分區樹來存儲空間中的所有點。這些數據結構有效地（通常在次線性時間內）支持形式爲「什麼是最接近點p？」的查詢。然後，您可以執行以下操作：

1. 爲空間中的點構建空間分區樹。
2. 使用樹找到最接近你的起點的點p。
3. 重複以下步驟：
   1. 移至點p。
   2. 從樹上刪除p。
   3. 將p設置爲距離您當前位置最近的點。

希望這有助於！