有两组点，称集合A和集合B，对于集合A中的每个点a，尝试得到B的子集sub_B，即sub_B中b与a的距离小于b与b的距离和任何其他 A 点。点是二维的。例如A = { (0,0), (3,0) }, B = { (1,1), (2,1) }，则对于A中的(0,0)，其集合为{( 1,1)}，对于A中的(3,0)，其集合为{(2,1)}。显然，蛮力方法可以获得 O(mn) 的结果，其中 m 是 A 的大小，n 是 B 的大小。我的问题是是否有更好的解决方案？
最佳答案
集合A中的所有点可以排列成一个Space Paritioned Tree并且 B 中的每个点都可以用作查询来查找集合 A 中的最近邻居并获取距离最小的所有点集。这给出了一个使用 kd 树的 O(N*log(N)+M*log(N)) 解决方案。
关于algorithm - 两组点之间的最近点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19992745/