Approximate minimum-weight matching with outliers under translation
Conference Paper
Our goal is to compare two planar point sets by finding subsets of a given size such that a minimum-weight matching between them has the smallest weight. This can be done by a translation of one set that minimizes the weight of the matching. We give efficient algorithms (a) for finding approximately optimal matchings, when the cost of a matching is the L -norm of the tuple of the Euclidean distances between the pairs of matched points, for any p ∈ [1,∞], and (b) for constructing small-size approximate minimization (or matching) diagrams: partitions of the translation space into regions, together with an approximate optimal matching for each region. p
Full Text
Duke Authors
Cited Authors
- Agarwal, PK; Kaplan, H; Kipper, G; Mulzer, W; Rote, G; Sharir, M; Xiao, A
Published Date
- December 1, 2018
Published In
Volume / Issue
- 123 /
International Standard Serial Number (ISSN)
- 1868-8969
International Standard Book Number 13 (ISBN-13)
- 9783959770941
Digital Object Identifier (DOI)
- 10.4230/LIPIcs.ISAAC.2018.26
Citation Source
- Scopus