Поиск K минимальных расстояний между точками в 3D

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))