兩組點之間的最近點

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中的所有點都可以排列成Space Paritioned Tree，並且B中的每個點都可以用作查詢來查找集合A中最近的鄰居並獲取所有具有最小距離的點集合。這使用kd-trees給出了一個O（N * log（N）+ M * log（N））解。