具有周期性边界条件的最近邻居搜索 [英] Nearest neighbor search with periodic boundary conditions

问题描述

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

In a cubic box I have a large collection points in R^3. I'd like to find the k nearest neighbors for each point. Normally I'd think to use something like a k-d tree, but in this case I have periodic boundary conditions. As I understand it, a k-d tree works by partitioning the space by cutting it into hyper planes of one less dimension, i.e. in 3D we would split the space by drawing 2D planes. For any given point, it is either on the plane, above it, or below it. However, when you split the space with periodic boundary conditions a point could be considered to be on either side!

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

What's the most efficient method of finding and maintaining a list of nearest neighbors with periodic boundary conditions in R^3?

逼近是不够的，这些点一次只能移动一个(想想蒙特卡洛不是N体模拟).

Approximations are not sufficient, and the points will only be moved one at a time (think Monte Carlo not N-body simulation).

推荐答案

即使在欧几里得的情况下，一个点及其最近的邻居也可能位于超平面的相对两侧. k-d树中最邻近搜索的核心是确定点与框之间距离的图元.对于您的案例，唯一必要的修改就是考虑到环绕的可能性.

Even in the Euclidean case, a point and its nearest neighbor may be on opposite sides of a hyperplane. The core of nearest-neighbor search in a k-d tree is a primitive that determines the distance between a point and a box; the only modification necessary for your case is to take the possibility of wraparound into account.

或者，您可以实现覆盖树，该覆盖树可用于任何度量标准.

Alternatively, you could implement cover trees, which work on any metric.

这篇关于具有周期性边界条件的最近邻居搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！