nearest-neighbor - 最近邻 - k-d 树 - 维基百科证明

Question

关于 wikipedia entry for k-d trees ，提出了一种在 k-d 树上进行最近邻搜索的算法。我不明白的是步骤 3.2 的解释。仅仅因为搜索点与当前节点的分割坐标之差大于搜索点与当前最佳点的分割坐标之差，你怎么知道没有更近的点呢？

Nearest neighbor search Animation of NN searching with a KD Tree in 2D

The nearest neighbor (NN) algorithm aims to find the point in the tree which is nearest to a given input point. This search can be done efficiently by using the tree properties to quickly eliminate large portions of the search space. Searching for a nearest neighbor in a kd-tree proceeds as follows:

1. Starting with the root node, the algorithm moves down the tree recursively, in the same way that it would if the search point were being inserted (i.e. it goes right or left depending on whether the point is greater or less than the current node in the split dimension).
2. Once the algorithm reaches a leaf node, it saves that node point as the "current best"
3. The algorithm unwinds the recursion of the tree, performing the following steps at each node: 1. If the current node is closer than the current best, then it becomes the current best. 2. The algorithm checks whether there could be any points on the other side of the splitting plane that are closer to the search point than the current best. In concept, this is done by intersecting the splitting hyperplane with a hypersphere around the search point that has a radius equal to the current nearest distance. Since the hyperplanes are all axis-aligned this is implemented as a simple comparison to see whether the difference between the splitting coordinate of the search point and current node is less than the distance (overall coordinates) from the search point to the current best. 1. If the hypersphere crosses the plane, there could be nearer points on the other side of the plane, so the algorithm must move down the other branch of the tree from the current node looking for closer points, following the same recursive process as the entire search. 2. If the hypersphere doesn't intersect the splitting plane, then the algorithm continues walking up the tree, and the entire branch on the other side of that node is eliminated.
4. When the algorithm finishes this process for the root node, then the search is complete.

Generally the algorithm uses squared distances for comparison to avoid computing square roots. Additionally, it can save computation by holding the squared current best distance in a variable for comparison.

Answer 1

仔细看animation on that page的第6帧.

当算法返回递归时，它所在的超平面的另一侧可能有一个更近的点。我们已经检查了一半，但另一半可能还有更接近的点。

好吧，事实证明我们有时可以进行简化。如果另一半上不可能有一个点比我们当前的最佳(最近)点更近，那么我们可以完全跳过那半个超平面。这种简化是第 6 帧所示的简化。

通过比较从超平面到我们搜索位置的距离来确定这种简化是否可行。因为超平面与轴对齐，从它到任何其他点的最短线将是一条沿一维的线，因此我们可以只比较超平面 split 的维度的坐标。

如果从搜索点到超平面的距离比从搜索点到当前最近点的距离更远，则没有理由搜索该分割坐标。

即使我的解释没有帮助，图形也会。祝你的项目好运!