CODEWITHSUNDEEP
algorithmgeometry
Chai ML
Chai ML

Reputation: 141

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

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!

Upvotes: 6

Views: 2120

Answers (1)

jonathanasdf
jonathanasdf

Reputation: 2894

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

Upvotes: 6

Related Questions