Minimize range of distances between two sets of points

Question

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.

Answer 1

Here is a simple algorithm to get you started.

Compute all $\binom{n}{2}$ pairwise distances, and put them in an array $A$. For each pair $a<b$ in $A$, use a bipartite matching algorithm to determine whether there is a matching that uses only distances in the range $[a,b]$. Choose the pair minimizing $b-a$. In total, there are $O(n^4)$ invocations of the matching algorithm.

It is easy to improve upon this. For example, for each $a$ we can find the best $b$ using binary search (this is essentially bottleneck matching), dropping the number of invocations down to $O(n^2\log n)$. You can improve this further (in practice) as follows:

• Let $a$ be the minimal element in $A$.
• Find the minimal $b$ such that an $[a,b]$-matching exists.
• Decrement $b$, and find the maximal $a$ such that an $[a,b]$-matching exists.
• Increment $a$, and find the minimal $b$ such that an $[a,b]$-matching exists.
• And so on, until no more matchings are possible.

Here an $[a,b]$-matching is one only using weights in $[a,b]$, and "increment/decrement" are relative to $A$.

You can probably improve this even further, even in this oblivious setting where we do not use the fact that the distances originate from a planar embedding of the points.