3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Please credit the original source where you encountered this task. Where did you encounter it? A contest? A textbook? The more context you can share, the more likely you will get a good answer. $\endgroup$ – D.W. Sep 19 '20 at 19:50
  • $\begingroup$ We discourage questions that are solely the statement of a contest-style task. We expect you to think about how to solve it and show us the best algorithm you've found so far. We're happy to help you understand the concepts but just solving exercises or contest-style problems for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Sep 19 '20 at 19:51
  • $\begingroup$ @D.W. This isn't actually a task that I found somewhere, just an abstraction of a problem I'm trying to solve in an online game. I edited the question to include what I tried, but I couldn't come up with a full algorithm (short of brute force). $\endgroup$ – apilat Sep 20 '20 at 9:55
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.