Algorithm for matching point sets

Question

I have two sets of points A and B, whereas the points can be 2D or 3D. Both sets have the same size n, which is rather low (5 - 20).

I would like to know how well these sets agree. That is, ideally I would find pairings between the points such that the sum of all Euclidean pair distances d(A,B) is minimal. So

d(A,B) = \sum_{i=1}^n ||A_i - B_i||_2

The final outcome is used to compare with other point sets. So, for example:

• A = (1,1), (1,2), (1,3)
• B = (1,1), (2,2), (1,3)

would give me d(A,B) = 1.

• C = (1,1), (2,1), (3,1)
• D = (2,1), (2,2), (3,1)

would give me d(C,D) = 1.414.

Any good ideas?

Answer 1

You can for example model your problem as an assignment problem (Wikipedia link), where you define the cost C_ij of assigning point A_i (from set A) to point B_j (from set B) to be equal to the distance between them. This assignment problem can then be solved using the Hungarian algorithm (Wikipedia link).