Paper Info
Title
Approximate Minimum-Weight Matching with Outliers under Translation.
Abstract
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 $pin [1,infty]$, 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.
Year
DOI
Venue
2018
10.4230/LIPIcs.ISAAC.2018.26
ISAAC
DocType
Volume
Citations 
Conference
abs/1810.10466
0
PageRank 
References 
Authors
0.34
0
7
Name
Order
Citations
PageRank
Pankaj K. Agarwal15257593.81
Haim Kaplan23581263.96
Geva Kipper300.34
Wolfgang Mulzer425736.08
Günter Rote51181129.29
Micha Sharir684051183.84
Allen Xiao731.09