Let $P$ be a set of at most $n$ points and let $R$ be a set of at most $n$ geometric ranges, such as for example disks or rectangles, where each $p \in P$ has an associated supply $s_{ p} > 0$, and each $r \in R$ has an associated demand $d_{ r} > 0$. A (many-to-many) matching is a set $\mathcal{ A}$ of ordered triples $(p,r,a_{ pr}) \in P \times R \times \mathbb{ R}_{ >0}$ such that $p \in r$ and the $a_{ pr}$'s satisfy the constraints given by the supplies and demands. We show how to compute a maximum matching, that is, a matching maximizing $\sum_{ (p,r,a_{ pr}) \in \mathcal{ A}} a_{ pr}$. Using our techniques, we can also solve minimum bottleneck problems, such as computing a perfect matching between a set of $n$ red points $P$ and a set of $n$ blue points $Q$ that minimizes the length of the longest edge. For the $L_\infty$-metric, we can do this in time $O(n^{ 1+\varepsilon})$ in any fixed dimension, for the $L_2$-metric in the plane in time $O(n^{ 4/3 + \varepsilon})$, for any $\varepsilon > 0$.
Categories: cs.CG