Thread: Point assignment problem

Hi everyone,

I've got the following problem and I hope someone can help:

I've got two sets of data points in Euclidean space. Both sets have the same number of data points. I now want to assign each point of set 1 to a point of set 2, so that the sum of the distances between the pairs of data points is minimal. Also, no two points of set 1 should be assigned to the same point of set 2 (i.e. there should be no point in any of the two sets that's not assigned to a point of the other set).

I would assume that the problem can be solved using some sort of dynamic programming algorithm. When you set up a distance matrix between the two sets, this problem is equivalent to finding the minimum sum of N distance values with the constraint that none of the distance values was taken from the same row or column (N being the number of data points in each set).

Has anyone any ideas how to solve this?

Best,
K.

Take a look at the Hungarian algorithm, which is designed to solve just such an assignment problem as you have there.

Thanks Adrian, that's exactly what I was looking for.

If anyone else has the same problem, I found a nice website (apart from the wikipedia page) that explains the problem with some visualizations and provides different solutions.

You're welcome! Have a good one. Thanks for the link.