Geek Answers Handbook

Find the correspondence of a point between two points that minimize the sum of the distance of all matches

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

+6
source share
1 answer

Yes, the Hungarian algorithm for weighted bipartisan correspondence.

For each edge between an element from A and an element from B, let the weight of this edge be the distance between them. Then run the Hungarian algorithm to minimize the total weight.

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

+6
source

More articles:


All Articles