2D 平面中任意点（除自身之外）的最近邻点

Question

给定一个 2D 平面和 N 个点 (n1=(x1,y1), n2=(x2,y2)..., nN=(xN,yN))，什么是快速（O(n) 或更好）算法将找到任何点的最近邻居（例如n1最近邻居是n3，n2最近邻居是n4）。我正在考虑将其存储在字典中，其中键是点，值是邻居。SO 上似乎有很多类似的问题，但我找不到任何 Python 代码或非其他语言的答案。

Answer 1

平均而言，可以产生比 O(n) 更好的结果的简单解决方案是使用kd 树来存储点。构建树的最坏情况复杂度为 O(nlogn)。之后的搜索平均为O(logn)，最坏情况为 O(n) （通常对于远离所有其他数据的点）。

此外，您可能对 LSH 或局部敏感散列感兴趣，虽然它是一种近似方法，这意味着您不会总是得到正确的答案，对于高维数据，它提供了重要的加速，其复杂性与所选参数密切相关。

Answer 2

对于给定的点P，简单的解决方案：

• 计算 P 与所有其他点的距离，时间复杂度为 O(n)。

• 将它们保存为元组列表（或类似的数据结构），即（点，距 P 的距离）的元组。

• 遍历列表即可获得前 K 个最接近的点，时间复杂度为 O(n)。

第二种解决方案会花费更多的空间复杂度 (O(n^2)) 和随着时间的推移进行维护，但会缩短查找 K 个最近邻居的时间：

• 将每个点的字典保存为按距离排序的点列表（或类似的数据结构） - 构建此表一次的时间复杂度为 O(n^2 * log(n))。

• 查找 K 个最近点的时间复杂度为 O(k) - 字典访问 + 从有序列表中复制 k 个元素。

• 时间复杂度的开销在于以一种保持该数据结构有效的方式添加新点或删除旧点 - 两者都为 O(n*log(n))。

您选择的解决方案应该针对您想要优化的内容