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?

How do you achieve d(C,D) = 2 ? What inter-point distance do you use ? Check cs.smith.edu/~orourke/TOPP/P6.html — user1196549
– user1196549, Commented Jan 20, 2015 at 17:27
The formula that you are using to calculate d(a,b) is not at all obvious. Please clarify. — RBarryYoung
– RBarryYoung, Commented Jan 20, 2015 at 20:12
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
– ypnos, Commented Jan 20, 2015 at 20:14
Hidden behind the scenes here is a graph problem (bipartite matching with minimum cost) : en.wikipedia.org/wiki/Hungarian_algorithm — Rerito
– Rerito, Commented Jan 21, 2015 at 12:52

Fanfan · Accepted Answer · 2015-01-20 20:20:43Z

4

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

answered Jan 20, 2015 at 20:20

Fanfan

1,1265 silver badges7 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

ypnos Over a year ago

Your answer is already very helpful. The algorithm is O(n^3). It would be great if there is a faster algorithm for my case.

ypnos Over a year ago

I realized that the Earth Mover's Distance, which I had mentioned in my question, also utilizes the Hungarian algorithm. However, it is using optimizations (e.g. the fact that costs stem from a metric). So it seems to be the best choice for me.

Collectives™ on Stack Overflow

Algorithm for matching point sets

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related