文章基本信息

标题：Approximate Minimum-Weight Matching with Outliers Under Translation
本地全文：下载
作者：Pankaj K. Agarwal ; Haim Kaplan ; Geva Kipper 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2018
卷号：123
页码：1-13
DOI：10.4230/LIPIcs.ISAAC.2018.26
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Minimum-weight partial matching; Pattern matching; Approximation