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


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

  1. for finding approximately optimal matchings, when the cost of a matching is the Lp-norm of the tuple of the Euclidean distances between the pairs of matched points, for any p≥1, including p=infinity, and
  2. 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.

other papers about this subject
Last update: January 16, 2019.