Efficient Algorithms for Geometric Partial Matching

Abstract

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}\Vert a-b{\Vert }_p^q$ where $\Vert \cdot {\Vert }_p$ is the $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)\mathrm{polylog}n)$ time, and a $(1+\epsilon )$-approximation algorithm that runs in $O((n+k\sqrt{k})\mathrm{polylog}n\cdot \log {\epsilon }^{-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,r{n}^{3/2}\}\mathrm{polylog}n)$ time.