I have an interesting problem for a project of mine. Let's say I have two sets of points which I'll call set A and set B. I want to group these in pairs, with one point from each set in each pair. If the two sets each contain the same number of points, then each point will only be used once, but if one set has fewer points than the other, then points in the smaller set may be reused to make up the difference. In either case, every point must be used. What I'm searching for is the set of pairs where the sum total of the distances between the points in each pair is as small as possible.
For a simple example, suppose I have the following points in sets A and B:
| A | B |
|---|---|
| c (2, 4) | f (3, 1) |
| d (3, 3) | g (6, 5) |
| e (5, 2) |
There are six possible groups of pairs using all of these points (the order doesn't matter). I've listed them below, with the distances between the points in each pair added up.
{{c, f}, {d, f}, {e, g}} = 3.162 + 2 + 3.162 = 8.325
{{c, f}, {d, g}, {e, f}} = 3.162 + 3.606 + 2.236 = 9.004
{{c, g}, {d, f}, {e, f}} = 4.123 + 2 + 2.236 = 8.359
{{c, f}, {d, g}, {e, g}} = 3.162 + 3.606 + 3.162 = 9.930
{{c, g}, {d, f}, {e, g}} = 4.123 + 2 + 3.162 = 9.285
{{c, g}, {d, g}, {e, f}} = 4.123 + 3.606 + 2.236 = 9.965
The first of these sets has the smallest total distance, so that would be the correct result. I plan to solve this problem programmatically. I could potentially write an algorithm to go through each combination like I've done here, but it would become completely unrealistic for the amount of processing time it would take with very large sets. I want a solution that will work for sets containing thousands of points in 3D space. I feel like there has to be a better way to do this. Unfortunately, something as simple as grouping each point with it's nearest neighbor doesn't work. As you can see in the example above, all three points in set A are closer to point f than point g.
Can in anyone think of a possible a mathematic process to determine which point from from set A should be associated with which point from set B?
Thanks in advance!
Best Answer
This is exactly the assignment problem with points in one set being agents, the other set's points being tasks and the cost of an agent/task combination being the Euclidean distance. For equal set sizes it may be solved in polynomial time using e.g. the Hungarian algorithm.
For unequal set sizes find an optimal matching between all points of the smaller set (say $A$) and an equal number of points of the larger set ($B$); for the remaining unmatched $B$-points simply pair each with the closest $A$-point.