I have two sets of n
points each in 2D Cartesian coordinates. I want to find a one-to-one pairing between the points in sets A
and B
such that the range of distances between the points is the smallest.
For example, consider $n=3$, $A_1 = (0,0)$, $A_2 = (1,0)$, $A_3 = (3,0)$, $B_1 = (1,1)$, $B_2 = (3,2)$, $B_3 = (-1,0)$. The best pairing will is $A_1 \text{ and } B_1$, $A_2 \text{ and } B_3$, $A_3 \text{ and } B_2$, because the distances are $(\sqrt{2}, 2, 2)$, giving the smallest range of $2 - \sqrt2$.
Ideally, I am looking for a solution which is able to solve the problem quickly (<5 seconds) for $n=300$.
The naive solution of trying all n!
permutations is clearly too slow. I also thought about finding all n^2
combinations of distances, sorting them, and then removing the extremes until no possible pairing exists, but I don't know how to determine whether removing one possible connection will make it so no pairing exists.