patternMinor
Minimize range of distances between two sets of points
Viewed 0 times
minimizerangepointstwobetweendistancessets
Problem
I have two sets of
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 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.Solution
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 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:
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.
Compute all $\binom{n}{2}$ pairwise distances, and put them in an array $A$. For each pair $a 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.
Context
StackExchange Computer Science Q#130316, answer score: 4
Revisions (0)
No revisions yet.