在超球面上，离另一点最近的点是什么？

Question

5

我有n个点（约10^5个），位于m维（在10^4到10^6之间）的超球体上。

我将进行一系列查询，形式为“给定点p，找到最接近p的n个点中的一个”。我将进行大约n个这样的查询。

（不确定超球面事实是否有所帮助。）

解决此问题的简单且朴素的算法是，对于每个查询，将p与所有其他n个点进行比较。做n次这样的操作会得到O(n^2m)的运行时间，这太大了，我无法计算。

有更高效的算法可以使用吗？如果我能够通过某些对数因子将其降低到O(nm)，那就太好了。

- michael dillard

2个回答

0

将您的空间划分为高维立方体 - 称之为单元格 - 平均具有每个单元格一个点的边缘大小。您将需要从超单元格到它们包含的点集的映射。

然后，给定一个点，请检查其所在的超单元格是否有其他点。如果为空，请查看相邻的超单元格（为简单起见，我建议使用超单元格的文字超立方体，而不是一些由超单元格组成的超球体）。检查其中是否有其他点。不断重复直到找到一个点为止。假设您的点是随机分布的，则很有可能在1-2次扩展内找到第二个点。

一旦找到一个点，请检查可能包含更近点的所有超单元格。这是可能的，因为您发现的点可能在角落里，但是在迄今为止检查过的所有超单元格包含的超立方体外面有一些更近的点。

- Dave

2

这种方法在2-3维度中效果很好。但在10,000维度中并不那么理想，因为每个点最终都会落入一个无法比较的超立方体中，所以你最终还是需要检查每个点。 - btilly

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- btilly · Accepted Answer

也许不行。拥有许多维度会使索引变得极其困难。这就是为什么人们寻找机会将维度数量减少到可管理的范围内的原因。