在 3D 模式下搜索点之间的 K 最小距离

Question

我在 3D 中有两个不相交的点集。我需要找到具有最小距离的k对点。每个点都有 (x， y， z( 坐标。

一致性：解决方案必须是串行最优解决方案。请不要多线程。可以使用诸如分而治之/动态规划之类的方法。

我目前的方法是：

listOfPairs = []
for all points a in setA
for all points b in setB
distance = calcDistance(a, b)
listOfPairs.append((a, b, distance))
sortByDistance(distance) // using the built in sort method
PrintPointsAndDistances(listOfPairs, k) // print the first k elements

谢谢。

Answer 1

这可以通过优先级队列来完成。正如你所做的那样

priorityQueue = PriorityQueue(k) // of size k
for all points a in setA
for all points b in setB
distance = calcDistance(a, b)
priorityQueue.push_with_priority((a, b), distance)

剩下的是 k 个最短距离对，算法将以 Θ(N*log(k(( 运行