Minimum Partial-Matching and Hausdorff RMS-Distance under Translation: Combinatorics and Algorithms

DOI10.1007/978-3-662-44777-2_9MaRDI QIDQ2921397zbMATH OpenOpenAlexFDO

Authors Rinat Ben-Avraham, Rafel Jaume, Balázs Keszegh, Orit E. Raz, Igor Tubis, Matthias Henze, Micha Sharir

Publication date 8 October 2014

Published in Algorithms - ESA 2014 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.7273, http://real.mtak.hu/15176/1/esa2014_edit10.pdf

zbMATH Keywords

Hausdorff RMS-distancelocal minimumpartial matchingpolyhedral subdivision

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: We consider the RMS distance (sum of squared distances between pairs of points) under translation between two point sets in the plane, in two different setups. In the partial-matching setup, each point in the smaller set is matched to a distinct point in the bigger set. Although the problem is not known to be polynomial, we establish several structural properties of the underlying subdivision of the plane and derive improved bounds on its complexity. These results lead to the best known algorithm for finding a translation for which the partial-matching RMS distance between the point sets is minimized. In addition, we show how to compute a local minimum of the partial-matching RMS distance under translation, in polynomial time. In the Hausdorff setup, each point is paired to its nearest neighbor in the other set. We develop algorithms for finding a local minimum of the Hausdorff RMS distance in nearly linear time on the line, and in nearly quadratic time in the plane. These improve substantially the worst-case behavior of the popular ICP heuristics for solving this problem.

Recommendations

• Partial-matching RMS distance under translation: combinatorics and algorithms
• Minimum many-to-many matchings for computing the distance between two sequences
• A new algorithm for computing the minimum Hausdorff distance between two point sets on a line under translation
• On the Hamming distance in combinatorial optimization problems on hypergraph matchings
• Minimizing the weighted directed Hausdorff distance between colored point sets under translations and rigid motions
• Minimizing the Weighted Directed Hausdorff Distance between Colored Point Sets under Translations and Rigid Motions
• Computing the minimum Hausdorff distance between two point sets on a line under translation
• On minimum maximal distance-\(k\) matchings
• On minimum maximal distance-\(k\) matchings
• Minimum-weight perfect matching for nonintrinsic distances on the line

Cited in

(13)

• Small candidate set for translational pattern search
• Bipartite diameter and other measures under translation
• Set systems related to a house allocation problem
• FPTAS for Minimizing Earth Mover’s Distance under Rigid Transformations
• Bottleneck partial-matching Voronoi diagrams and applications
• Linear transformation distance for bichromatic matchings
• scientific article; zbMATH DE number 820058 (Why is no real title available?)
• scientific article; zbMATH DE number 7610223 (Why is no real title available?)
• Bipartite diameter and other measures under translation
• Approximate minimum-weight matching with outliers under translation
• Partial-matching RMS distance under translation: combinatorics and algorithms
• Counting houses of Pareto optimal matchings in the house allocation problem
• Bottleneck partial-matching Voronoi diagrams and applications

This page was built for publication: Minimum Partial-Matching and Hausdorff RMS-Distance under Translation: Combinatorics and Algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2921397)