Geometric Matching and Bottleneck Problems

Abstract

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+\epsilon })$ in any fixed dimension, for the $L_2$-metric in the plane in time $O(n^{4/3+\epsilon })$, for any $\epsilon >0$.