algorithm - 在 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个距离最短的pair，算法会运行在Θ(N*log(k))