 License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2019.6
URN: urn:nbn:de:0030-drops-104109
URL: https://drops.dagstuhl.de/opus/volltexte/2019/10410/
 Go to the corresponding LIPIcs Volume Portal

### Efficient Algorithms for Geometric Partial Matching

 pdf-format:

### Abstract

Let A and B be two point sets in the plane of sizes r and n respectively (assume r <= n), and let k be a parameter. A matching between A and B is a family of pairs in A x 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 ||*||_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)polylog n) time, and a (1 + epsilon)-approximation algorithm that runs in O((n + k sqrt{k})polylog n * 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, rn^{3/2}}polylog n) time.

### BibTeX - Entry

```@InProceedings{agarwal_et_al:LIPIcs:2019:10410,
author =	{Pankaj K. Agarwal and Hsien-Chih Chang and Allen Xiao},
title =	{{Efficient Algorithms for Geometric Partial Matching}},
booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
pages =	{6:1--6:14},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-104-7},
ISSN =	{1868-8969},
year =	{2019},
volume =	{129},
editor =	{Gill Barequet and Yusu Wang},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
DROPS-Home | Fulltext Search | Imprint | Privacy 