algorithm - 在二维空间中找到最近的点

Question

昨天看了一个问题，稍微修改一下就可以翻译成下面的问题:

点的坐标在二维空间中用 (x, y) 表示。

输入:点数组 ARRAY = (x1, y1), (x2, y2), (x3, y3), ..., (xn, yn) 和另一个点 D = (xi, yi)

在 ARRAY 中找到距离 D 最近的点。

“最近”指的是 Euclidian distance .

---

有一个明显的解决方案:遍历ARRAY 中的每个点并计算它到D 的欧几里得距离。然后，找到最短的距离。这可以在 O(N) 时间内完成。

我们可以在 O(logN) 中做得更快吗？我正在尝试使用分而治之的方法，但还没有得出具体的想法。

---

问题的概括:如何在 K 维空间中找到最近的点？我们可以在不到 O(N) 的时间内完成吗？

Answer 1

如果数组未以任何方式排序，则不可能比 O(n) 更快，因为您必须检查每个点以确保它不比您目前找到的任何点更近。

您可以进行一些预处理以对点进行排序或将它们打包到某种结构中，然后对该结构进行搜索。在这种情况下，虽然预处理步骤可能比 O(n) 慢，但单个搜索可能更快。如果您有许多点要对照同一组点进行检查，这可能是有利的。