CODEWITHSUNDEEP
algorithmmathoptimizationsetdistance
Arjun C
Arjun C

Reputation: 357

Searching for K minimum distances between points in 3D

I have two disjoint-sets of points in 3D. I need to find the k pair of points with the minimum distances. Each point has (x, y, z) coordinates.

Constaints: The solution has to be a serial optimal solution. No multithreading please. Approaches such as divide and conquer/dynamic programming can be used.

My current approach is:

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

Thanks.

Upvotes: 1

Views: 250

Answers (1)

Bob Bills
Bob Bills

Reputation: 519

This can be done with a priority queue. As you have done

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)

What you are left are the k shortest distance pairs, and the algorithm will run in Θ(N*log(k))

Upvotes: 1

Related Questions