# Efficient algorithms for geometric partial matching

Conference Paper

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 × B so that any point of A ∪ 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) = Σ ‖a-b‖ where ‖·‖ is the L -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 -norm matching objective: An exact algorithm that runs in O((n + k ) polylog n) time, and a (1 + ε)-approximation algorithm that runs in O((n + k√k) polylog n· log ε ) 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 , rn }polylog n) time. (a,b)ϵ M p p p p q 2 −1 2 3/2

### Full Text

### Duke Authors

### Cited Authors

- Agarwal, PK; Chang, HC; Xiao, A

### Published Date

- June 1, 2019

### Published In

### Volume / Issue

- 129 /

### International Standard Serial Number (ISSN)

- 1868-8969

### International Standard Book Number 13 (ISBN-13)

- 9783959771047

### Digital Object Identifier (DOI)

- 10.4230/LIPIcs.SoCG.2019.6

### Citation Source

- Scopus