8年前。
This question was migrated from Software Engineering Stack Exchange because it can be answered on Stack Overflow. Migrated。
我需要解决一个计算问题，归结为在两个集合之间寻找相互最近的点对。问题是这样的：
给定欧几里德空间中的一组点a和一组点b，找到所有对（a，b），使得b是b中离a最近的点，a是a中离b最近的点。
集合A和B大约相等大小，我们将称这个大小N为我的特定问题N大约为250000。
蛮力解决方案是将每个点与每一个具有二次时间复杂度的点进行比较。有没有更有效的算法来做这个？
最佳答案
当我不得不进行近邻搜索时，我发现一个非常有用的数据结构是kd树。Wikipedia有一个很好的概述，this是一个很好的深入讨论的算法，如果你正在实现自己的（虽然一个图书馆可能已经存在了-你没有提到你正在使用的语言）。kd树最重要的一点是它允许在o（log n）时间内执行最近的负向搜索。
这样，您可以在a-in-o（n logn）时间内生成两个列表-a的成员及其在b中的近邻，b的成员及其近邻。然后，您可以比较列表以查看哪些对匹配。做得很幼稚，这是o（n^2），尽管你可能会想到一种更快的方法。
[编辑]你让我想到了；这是我的第二个想法：
for(a in A)
b := nearest(B, a)
if a = nearest(A, b)
add (a, b) to results
end if
end for
function nearest(X, y)
return nearest member of set X to point y
end function
据我估计，那是o（n logn）。
关于algorithm - 给定两个(大)点集，如何有效地找到彼此最接近的对？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/5077318/