algorithm - 两组点之间的最近点

Question

有两组点，即集合A和B，对于集合A中的每个点a，尝试得到B的一个子集sub_B，即sub_B中的b与a的距离小于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 的大小。我的问题是是否有更好的解决方案？

Answer 1

集合 A 中的所有点都可以排列成一个空间分区树，并且 B 中的每个点都可以作为查询来查找集合 A 中的最近邻，并获取所有距离最小的点集合。这给出了使用 kd-trees 的 O(N*log(N)+M*log(N)) 解决方案。