Geometric pattern matching for point sets in the plane under similarity transformations

DOI10.1016/j.ipl.2009.04.021zbMath1202.68447OpenAlexW1968602136MaRDI QIDQ989531

Dror Aiger, Klara Kedem

Publication date: 20 August 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2009.04.021

zbMATH Keywords

computational geometryapproximation algorithmsrandomized algorithmsHausdorff distancegeometric pattern matching

Mathematics Subject Classification ID

Searching and sorting (68P10) Pattern recognition, speech recognition (68T10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (4)

Efficient point pattern matching algorithm for planar point sets under transform of translation, rotation and scale ⋮ Geometric pattern matching reduces to \(k\)-SUM ⋮ Point pattern matching algorithm for planar point sets under Euclidean transform ⋮ Geometric Pattern Matching Reduces to k-SUM.

Cites Work

• Unnamed Item
• Geometric pattern matching under Euclidean motion
• Generalizing the Hough transform to detect arbitrary shapes
• The complexity of selection and ranking in X+Y and matrices with sorted columns
• Efficient partition trees
• The upper envelope of Voronoi surfaces and its applications
• Approximate decision algorithms for point set congruence
• Getting around a lower bound for the minimum Hausdorff distance
• Geometric applications of a randomized optimization technique
• Combinatorial and experimental methods for approximate point pattern matching
• Lower bounds for the complexity of the graph of the Hausdorff distance as a function of transformation
• On Approximating the Depth and Related Problems
• Linear Programming in Linear Time When the Dimension Is Fixed
• Matching Points into Pairwise-Disjoint Noise Regions: Combinatorial Bounds and Algorithms

This page was built for publication: Geometric pattern matching for point sets in the plane under similarity transformations