Algorithm for matching point sets

3
votes

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?

1
algorithmgeometrydynamic-programmingmathematical-optimization
How do you achieve d(C,D) = 2 ? What inter-point distance do you use ? Check cs.smith.edu/~orourke/TOPP/P6.html - Yves Daoust
Sorry that was a mistake. I would use euclidean distance. - ypnos
The formula that you are using to calculate d(a,b) is not at all obvious. Please clarify. - RBarryYoung
Your link lead me to this paper containing a compact description of the algorithm: Sayan Bhattacharya. A Survey on Algorithms for Euclidean Matching. db.cs.duke.edu/courses/cps234/fall08/projects/sayan_proj.pdf - ypnos
Hidden behind the scenes here is a graph problem (bipartite matching with minimum cost) : en.wikipedia.org/wiki/Hungarian_algorithm - Rerito

1 Answers

4
votes

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