Efficient Algorithms for Geometric Partial Matching

Let $A$ and $B$ be two point sets in the plane of sizes $r$ and $n$ respectively (assume $r\le n$), and let $k$ be a parameter. A matching between $A$ and $B$ is a family of pairs in $A\times B$ so that any point of $A\cup B$ appears in at most one pair. Given two positive integers $p$ and $q$, we define the cost of matching $M$ to be $c(M) = \sum_{(a, b) \in M}|{a-b}|_p^q$where$|{\cdot}|_p$isthe$L_p$-norm. The geometric partial matching problem asks to find the minimum-cost size-$k$ matching between $A$ and $B$. We present efficient algorithms for geometric partial matching problem that work for any powers of $L_p$-norm matching objective: An exact algorithm that runs in $O((n+k^2)n)$ time, and a $(1 + \varepsilon)$-approximationalgorithmthatrunsin$O((n + k\sqrt{k}) {\mathop{$\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}$}} n \cdot \log\varepsilon^{-1})$ time. Both algorithms are based on the primal-dual flow augmentation scheme; the main improvements involve using dynamic data structures to achieve efficient flow augmentations. With similar techniques, we give an exact algorithm for the planar transportation problem running in $O(\min{n^2, rn^{3/2}} {\mathop{$\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}$}} n)$ time.