具有周期性边界条件的最近邻搜索
在一个立方体盒子里，我有一个很大的 R^3 集合点。我想找到每个点的 k 个最近邻。通常我会考虑使用 kd 树之类的东西，但在这种情况下我有周期性边界条件。据我了解，kd 树的工作原理是通过将空间切割成一维较少的超平面来划分空间，即在 3D 中，我们将通过绘制 2D 平面来划分空间。对于任何给定的点，它要么在平面上，要么在平面上，要么在平面下。然而，当您使用周期性边界条件分割空间时，可以认为一个点位于任一侧！
在 R^3 中查找和维护具有周期性边界条件的最近邻居列表的最有效方法是什么？
近似值是不够的，并且一次只能移动一个点（认为蒙特卡罗而不是 N 体模拟）。
In a cubic box I have a large collection points in R^3. I'd like to find the k nearest neighbors for each point. Normally I'd think to use something like a k-d tree, but in this case I have periodic boundary conditions. As I understand it, a k-d tree works by partitioning the space by cutting it into hyper planes of one less dimension, i.e. in 3D we would split the space by drawing 2D planes. For any given point, it is either on the plane, above it, or below it. However, when you split the space with periodic boundary conditions a point could be considered to be on either side!
What's the most efficient method of finding and maintaining a list of nearest neighbors with periodic boundary conditions in R^3?
Approximations are not sufficient, and the points will only be moved one at a time (think Monte Carlo not N-body simulation).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
即使在欧几里得的情况下，一个点和它最近的邻居也可能位于超平面的相对两侧。 kd树中最近邻搜索的核心是确定点与框之间距离的原语；您的情况唯一需要的修改是考虑回绕的可能性。
或者，您可以实现适用于任何指标的覆盖树。
Even in the Euclidean case, a point and its nearest neighbor may be on opposite sides of a hyperplane. The core of nearest-neighbor search in a k-d tree is a primitive that determines the distance between a point and a box; the only modification necessary for your case is to take the possibility of wraparound into account.
Alternatively, you could implement cover trees, which work on any metric.
（尽管我不完全确定它有效，但我还是发布了这个答案。直观上似乎是正确的，但可能存在我没有考虑到的边缘情况）
如果您正在使用周期性边界条件，那么您可以认为空间被切割成一系列固定大小的块，然后将它们全部叠加在一起。假设我们处于 R2 中。那么一种选择是将该块复制九次，并将它们排列成该块的重复项的 3x3 网格。鉴于此，如果我们找到中心正方形中任何单个节点的最近邻居，那么要么
换句话说，我们只需将元素复制足够多次，以便点之间的欧几里得距离可以让我们找到模空间中的相应距离。
在 n 维中，您需要对所有点制作 3n 个副本，这听起来很多，但对于 R3 来说，仅比原始数据增加了 27 倍尺寸。这无疑是一个巨大的增长，但如果它在可接受的范围内，您应该能够使用此技巧来利用标准 kd 树（或其他空间树）。
希望这有帮助！ （并希望这是正确的！）
(I'm posting this answer even though I'm not fully sure it works. Intuitively it seems right, but there might be an edge case I haven't considered)
If you're working with periodic boundary conditions, then you can think of space as being cut into a series of blocks of some fixed size that are all then superimposed on top of one another. Suppose that we're in R2. Then one option would be to replicate that block nine times and arrange them into a 3x3 grid of duplicates of the block. Given this, if we find the nearest neighbor of any single node in the central square, then either
In other words, we just replicate the elements enough times so that the Euclidean distance between points lets us find the corresponding distance in the modulo space.
In n dimensions, you would need to make 3n copies of all the points, which sounds like a lot, but for R3 is only a 27x increase over the original data size. This is certainly a huge increase, but if it's within acceptable limits you should be able to use this trick to harness a standard kd-tree (or other spacial tree).
Hope this helps! (And hope this is correct!)