带周期性边界条件的最近邻居搜索

在立方体框中，我在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

带周期性边界条件的最近邻居搜索

回答

相关问题