我正在嘗試編寫一個空間數據結構（例如K-D tree或QuadTree），給定一個點，它會找到最接近它的點x。空間數據結構中的不同搜索方法
我上面提到的數據結構的問題是它們主要支持徑向/區域搜索。因此他們將獲得給定點/節點的半徑爲y的點。
改變這些結構搜索我想要的將是低效的。我假設我需要多次重複徑向搜索，從一個短的徑向距離開始，並且不斷增大，直到我想要的點數接近給定點爲止。當然，這打破了數據結構背後的全部目的。
幾乎所有的空間數據結構都運行在徑向搜索上。什麼是其他高效搜索方法我可以適用於QuadTree或我需要考慮的任何其他空間數據結構以實現我的意思嗎？有什麼建議麼？
我不確定你的假設是否正確。 Wikipedia article on kd-trees指示如何使用該結構來支持找到搜索點的最近鄰居x。是的，它基本上是找到最近鄰居x次的重複，但我不確定您是否有權通過kd-tree算法從算法中獲得更高效的性能。
如果這還不夠好，也許你需要將你的點存儲在不同的數據結構中。如果x很小且有界，則可以將點存儲在加權圖中，其中邊權重當然是點之間的距離。
如果x既不小也沒有界限，你可以使用一個簡單的空間細分爲k*m統一單元格（這裏的2D，如果需要，膨脹到3 + D）。對於每個搜索點直接進入包含它的單元格，找到同一單元格中的其他點。如果他們的x比單元格的邊界更靠近搜索點，那麼這些就是您要查找的內容。如果不是，則搜索近邊界另一側的單元格。
如果你發現自己需要同時支持徑向/地區搜索和X -nearest鄰居搜索它不是世界的末日，如果你要保持2個數據結構，一個支持各類型的查詢。對於許多搜索問題，有效解決方案的第一步是將數據放入正確的結構中進行高效搜索。做出這個決定取決於你根本沒有提供給我們的數字。
如果您確實在四叉樹上多次調用搜索方法（這是我已經做了幾次），那麼如果您在每次調用中加倍搜索半徑直到您有正確的點數，搜索並不是那麼低效。假設2d空間，如果包含X點的正確最小半徑是R1，並且你繼續加倍直到找到包含它們的半徑R2，那麼（a）R2必須小於2xR1，並且（b） ）搜索區域在每次搜索時會變大4倍，這（我認爲）會給您提供一種最糟糕的情況，只有您通過實際搜索不到的區域（或其附近）搜索到的區域的一半。