Approximate minimum-weight matching with outliers under translation

Published

Conference Paper

© Pankaj K. Agarwal, Haim Kaplan, Geva Kipper, Wolfgang Mulzer, Günter Rote, Micha Sharir, and Allen Xiao; 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 p -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.

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