二维平面中任何点（除自身以外）的最近邻点

Question

给定一个二维平面和N个点（n1=（x1，y1），n2=（x2，y2）…，nN=（xN，yN）），将查找任何点的最近邻的快速（O（N）或更好）算法是什么（例如，n1最近邻是n3，n2最近邻是n4）。我在考虑将其存储在一个字典中，其中键是点，值是邻居

似乎有很多类似的问题，但我找不到Python中的任何代码或其他语言中没有的答案

Answer 1

对于给定的点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））

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

Answer 2

一个简单的解决方案可以产生比O（n）平均更好的结果，即使用k-d树存储点。构建树的最坏情况复杂性为O（nlogn）。之后的搜索是平均O（logn）和最坏情况O（n）（通常用于远离所有其他数据的点）

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