在一个立方体中，我在 R^3 中有一个很大的收集点。我想为每个点找到 k 个最近的邻居。通常我会考虑使用类似 k-d 树的东西，但在这种情况下，我有周期性的边界条件。据我了解，k-d 树的工作原理是通过将空间切割成少一维的超平面来划分空间，即在 3D 中，我们将通过绘制 2D 平面来分割空间。对于任何给定的点，它要么在平面上，要么在其上方，要么在其下方。但是，当您使用周期性边界条件分割空间时，可以认为一个点位于任一侧!
在 R^3 中查找和维护具有周期性边界条件的最近邻居列表的最有效方法是什么？
近似值是不够的，一次只能移动一个点(想想蒙特卡罗而不是 N 体模拟)。
最佳答案
即使在欧几里得情况下，一个点和它的最近邻点也可能在超平面的两侧。 k-d树中最近邻搜索的核心是一个原语，它决定了一个点和一个框之间的距离；您的情况唯一需要的修改是考虑环绕的可能性。
或者，您可以实现适用于任何指标的覆盖树。
关于algorithm - 具有周期性边界条件的最近邻搜索，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/6917664/