algorithm - 具有周期性边界条件的最近邻搜索

Question

在一个立方体盒子里，我有一个 R^3 的大收集点。我想为每个点找到 k 个最近的邻居。通常我会考虑使用像 k-d 树这样的东西，但在这种情况下我有周期性的边界条件。据我了解，k-d 树的工作原理是通过将空间切割成维数较少的超平面来划分空间，即在 3D 中，我们将通过绘制 2D 平面来分割空间。对于任何给定的点，它要么在平面上，要么在其上方，要么在其下方。但是，当您使用周期性边界条件分割空间时，可以认为一个点位于任一侧!

在 R^3 中查找和维护具有周期性边界条件的最近邻居列表的最有效方法是什么？

近似值是不够的，并且一次只能移动一个点(想想蒙特卡洛而不是 N 体模拟)。

Answer 1

即使在欧几里得情况下，一个点及其最近的邻居也可能位于超平面的相对两侧。 k-d树中最近邻搜索的核心是确定点到框距离的原语；您的情况唯一需要修改的是考虑环绕的可能性。

或者，您可以实现适用于任何指标的覆盖树。