Bipartite Matching in the Plane

Question

I'm currently working on a problem that I came across:

You are given a set $B$ of $n$ points in the plane, and a set $R$ of $n$ points in the plane. Each point is given by its coordinates. I have to Suggest an $O(n^{3})$ time algorithm for determining if there is a perfect matching between them, with the constraint that each point in $R$ is matched to a point in $B$ point whose distance is at most 1 unit away.

I have tried solving using the minimum distance using bipartite algorithm but could not arrive at a solution. Can anyone provide me with any ideas?

Answer 1

This problem has been solved by Alon Efrat, Alon Itai and Matthew J. Katz in their paper Geometry Helps in Bottleneck Matching and Related Problems. The running time of the algorithm is $O(n^{1.5} \log n)$.

Answer 2

Using existing algorithms, you solve this with a basic network flow approach.

First construct a bipartite graph from the point sets where every point is a vertex in the graph and there is an edge between points $x$ and $y$ if $x\in R$, $y \in B$ and $d(x,y) \leq 1$. This takes $\mathcal{O}(n^{2})$ time.

Then we can apply the normal bipartite perfect matching algorithm, which uses a Maximum Flow approach:

• Add a source vertex $s$ and sink vertex $t$.
• Add all edges $su$ where $u \in R$.
• Add all edges $vt$ where $v \in B$
• Assign all edges a capacity of $1$ unit.

Then we have a flow network which has a flow of $n$ units if and only if there's a perfect matching between $R$ and $B$. Thus we can use any Max Flow algorithm we care to, but in particular the augmenting path algorithm, in this case, runs in time $\mathcal{O}(|V|\cdot|E|)$, which is at most $\mathcal{O}(n^{3})$.

Of course we can use any faster algorithm, and still answer the question positively.

Answer 3

In time $O(n^2)$, you can construct a bipartite graph that has an edge from $r\in R$ to $b\in B$ if, and only if, they're at distance at most $1$ from each other. Then, use any standard algorithm for matchings of bipartite graphs: even the simplest ones run in time $O(n^3)$.