12

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

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

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

4

2 回答 2

5

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

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

于 2011-08-02T20:34:03.380 回答
3

（即使我不完全确定它是否有效，我也会发布这个答案。直觉上它似乎是正确的，但可能有一个我没有考虑过的极端情况）

如果您正在使用周期性边界条件，那么您可以将空间视为被切割成一系列固定大小的块，然后全部叠加在一起。假设我们在 R 2中。然后一种选择是将该块复制九次，并将它们排列成一个 3x3 的块副本网格。鉴于此，如果我们在中心正方形中找到任何单个节点的最近邻居，那么

  1. 最近的邻居在中心广场内，在这种情况下，邻居是最近的邻居，或者
  2. 最近的邻居在中央广场以外的广场。在这种情况下，如果我们在中心正方形中找到邻居对应的点，则该点应该是周期边界条件下原始测试点的最近邻居。

换句话说，我们只是复制元素足够多次，以便点之间的欧几里得距离让我们在模空间中找到相应的距离。

在 n 维中，您需要对所有点制作 3 n 个副本，这听起来很多，但对于 R 3而言，仅比原始数据大小增加 27 倍。这当然是一个巨大的增长，但如果它在可接受的范围内，您应该能够使用这个技巧来利用标准的 kd-tree（或其他空间树）。

希望这可以帮助！（希望这是正确的！）

于 2011-08-03T00:54:49.433 回答