Bipartite Matching in the Plane

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?

• Are you allowed to use existing algorithms? There's a simple solution in that case. Commented May 5, 2014 at 3:18
• Yes, I was thinking about the hungarian algorithm Commented May 5, 2014 at 4:23
• What have you tried? Where did you get stuck? We want to help you with your specific problems, not just do your (home-)work. However, as it is we don't know what this problem is and thus how to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? Commented May 5, 2014 at 7:04
• Why is this question put on hold by a moderator? I think it is clear what the OP was asking for, furthermore the OP said what he had tried. Commented May 5, 2014 at 7:20
• @A.Schulz (You have to @-notify if you expect a reply.) It's true that the question includes a sentence of the form "I have tried..."; I just could not make enough sense of it to say that it's a "valid" attempt. Apparently, enough fellow users thought otherwise and reopened the question. :) Commented May 5, 2014 at 23:12

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)$.

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.

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)$.