## Pankaj Agarwal, Haim Kaplan, Geva Kipper, Wolfgang Mulzer, Günter Rote,
Micha Sharir, and Allen Xiao:

# Approximate minimum-weight matching with outliers under translation

In:
*29th International Symposium on Algorithms and Computation
(ISAAC 2018)*, Jiaoxi, Yilan, Taiwan, December 2018. Editors: Wen-Lian
Hsu, Der-Tsai Lee, and Chung-Shou Liao. Leibniz International Proceedings
in Informatics (LIPIcs), Schloss Dagstuhl-Leibniz-Zentrum für
Informatik, 2015, Vol. **123**, pp. 26:1–26:13. doi:10.4230/LIPIcs.ISAAC.2018.26 →BibTeX
### 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

- 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, including `p`=infinity, and - 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.

Last update: January 16, 2019.