帶週期性邊界條件的最近鄰居搜索

在立方體框中，我在R^3中有一個大的收集點。我想找到每個點的k個最近鄰居。通常我會考慮使用類似於k-d樹的東西，但在這種情況下，我有周期性的邊界條件。據我瞭解，k-d樹通過將空間切割成一個較小維的超平面來劃分空間，即在3D中我們將通過繪製2D平面來分割空間。對於任何給定的點，它要麼在飛機上，要麼在其上面，要麼在其下面。然而，當你用週期性的邊界條件分割空間時，一個點可以被認爲是在任何一邊！帶週期性邊界條件的最近鄰居搜索

在R^3中找到並維護具有周期邊界條件的最近鄰居列表的最有效方法是什麼？

近似值不足，每次只移動一個點（想想Monte Carlo不是N體模擬）。

來源

2011-08-02 Hooked

我對「週期性邊界條件」一詞不熟悉。你能詳細解釋一下嗎？ – templatetypedef

通過一個例子可以很好地理解週期性邊界條件。在1D中，想象可能的點是從0到1.點0與點1相同。在.2和.3兩點之間的距離爲.1爲正常，但兩點之間的距離爲.1和。 9是2，因爲它循環。這對於更高維來推廣，x，y，z軸全部在3D中循環。 – Hooked

我在想，你有沒有設法實現這個？如果是這樣，你的速度有沒有提高？謝謝。 – sodiumnitrate

即使在歐幾里得情況下，一個點及其最近的鄰居可能位於超平面的相對兩側。 k-d樹中最近鄰居搜索的核心是確定點與盒子之間距離的基元;您的案例唯一必要的修改是考慮週轉的可能性。

或者，您可以實現覆蓋樹，它可以處理任何指標。

來源

2011-08-02 20:34:03 qwerty

（我張貼，即使我不能完全肯定它的工作原理這個答案。直覺似乎沒錯，但有可能是一個邊緣的情況我還沒有考慮過）如果你正在使用

週期性的邊界條件，那麼你可以把空間想象成一系列固定大小的塊，然後疊加在一起。假設我們在R 。然後一個選擇是將該塊複製9次，並將它們排列成塊的重複3×3網格。鑑於此，如果我們發現任何單個節點的近鄰中心廣場，然後要麼

最近的鄰居是中心廣場，在這種情況下，鄰居是近鄰，或
內部最近的鄰居在中心廣場以外的廣場上。在這種情況下，如果我們發現鄰居對應的中心點的點，那麼該點應該是週期性邊界條件下原始測試點的最近鄰點。

換句話說，我們只是複製元素足夠多的時間，以便點之間的歐幾里得距離讓我們在模數空間中找到相應的距離。

n維，你需要讓所有的點3 ^ñ份，其中聽起來很多，但對於R 只有27倍增幅比原始數據的大小。這當然是一個巨大的增長，但如果它在可接受的限度內，你應該能夠使用這個技巧來利用標準的kd-tree（或其他空間樹）。

希望這會有所幫助！（並且希望這是正確的！）

來源

2011-08-03 00:54:49 templatetypedef

帶週期性邊界條件的最近鄰居搜索

回答

相關問題