Approximate minimum-weight matching with outliers under translation

DOI10.4230/LIPICS.ISAAC.2018.26MaRDI QIDQ5091017zbMATH OpenFDO

Authors Haim Kaplan, Geva Kipper, Wolfgang Mulzer, Günter Rote, Allen Xiao, Pankaj K. Agarwal, Micha Sharir

Publication date 21 July 2022

Full work available at URL https://arxiv.org/abs/1810.10466

zbMATH Keywords

approximationminimum-weight partial matchingpattern matching

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Partial-matching RMS distance under translation: combinatorics and algorithms
• Approximate one-to-one point pattern matching
• Efficient algorithms for geometric partial matching
• Minimum Partial-Matching and Hausdorff RMS-Distance under Translation: Combinatorics and Algorithms
• Improved approximation bounds for planar point pattern matching

Cites work

• A near-linear time ε-approximation algorithm for geometric bipartite matching
• Algorithms for the transportation problem in geometric settings
• Dynamic Planar Voronoi Diagrams for General Distance Functions and their Algorithmic Applications
• Faster Scaling Algorithms for Network Problems
• Geographic quorum system approximations
• scientific article; zbMATH DE number 1424291 (Why is no real title available?)
• Matching point sets with respect to the earth mover's distance
• Minimum-cost flows in unit-capacity networks
• Partial-matching RMS distance under translation: combinatorics and algorithms
• Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications

This page was built for publication: Approximate minimum-weight matching with outliers under translation

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