能否在次二时间内找到所有点中最接近的点？

Question

3

一个算法问题。

输入：

是否存在一种算法，可以在次二次时间内返回数据点向量Y，使得Y[i]是X中距离X[i]最近的点？

显然，这可以在O(n^2)的时间内完成，因为您可以直接检查每个点。我想知道是否可能利用三角不等式来改进这个算法。我还对具有可证明边界的近似算法感兴趣（即像Y[i]这样的东西，距离X[i]的最小值不超过（1 + log(n))倍）。

- Jordan

1

澄清一下：Y[i] 应该是最接近 X[i] 但不是 X[i] 本身的点。否则，Y = X 将是完美的解决方案 :p - cadolphs

1个回答

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

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

- David Eisenstat · Accepted Answer

没有这样的算法。考虑一个度量，其中除一个点对之外的所有点距离都为1。这个点对不能在没有查询其特定距离预测器条目的情况下找到，这需要在最坏情况下进行Ω（n ^ 2）次查询。覆盖树可用于解决精确邻居问题。时间复杂度取决于度量的所谓“加倍维度”。