Search code examples
javaalgorithmclosest-points

Getting the best combination of closest pairs between 2 sets of points

I have to sets of points, lets say set A and B

  • A and B are equal in size
  • Every element of A is coupled to an element of B

All the points of A have to 'move' to an point of B, but an point of B cannot be coupled to multiple points of A.

I need to find the best combination, where the total (walk) distance (added up from the distance between each pair) is the minimal.

I made an example in Java for demonstration purposes (currently bruteforce every possible combination and check which has the smallest total distance)

Example 1

Example img 1

Example 2

Example img 2

Green rectangles represent a point in set A, Cyan rects represents a point in set B, ignore the orange square

How would I approach this?

Solution

  • This is an assignment problem, which can be solved in O(n³) time by the Hungarian algorithm. It should not be too hard to find source code or implement it yourself.