2026-07-23T19:43:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9974 2024-03-06T10:45:14Z ddc:004 open_access

Approximate Minimum-Weight Matching with Outliers Under Translation Agarwal, Pankaj K. Kaplan, Haim Kipper, Geva Mulzer, Wolfgang Rote, Günter Sharir, Micha Xiao, Allen Minimum-weight partial matching Pattern matching Approximation 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 in [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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pankaj K. Agarwal and Haim Kaplan and Geva Kipper and Wolfgang Mulzer and Günter Rote and Micha Sharir and Allen Xiao 2018 Is Part Of LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2018.26 urn:nbn:de:0030-drops-99747 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.26 eng https://creativecommons.org/licenses/by/3.0/legalcode