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

Question

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

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

近似是不够的,这些点只能一次移动一个(想想蒙特卡罗而不是N体模拟).

Answer 1

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

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