Find point correspondence between two point sets minimizing the sum of distance of all matches

Question

My question is, given two point sets A and B, element size of A is no more than that of B, is there any efficient way to find the corresponding point in B for each point in A, such that the sum of distance of all matches is minimal? Each point in B can be used no more than once. Thank you very much!

Answer 1

Yes, the Hungarian Algorithm for weighted bipartite matching.

For each edge between an element of A and an element of B, let the weight of that edge be the distance between them. Then, run the Hungarian Algorithm minimizing the total sum of the weights.

The total run time is O(|A|^3).