Shape matching under rigid motion
type: Item
instance of: scholarly article
title: Shape matching under rigid motion
zbMATH Open document ID: 1267.65024
author: Siu-Wing Cheng
author: Chi-Kit Lam
published in: Computational Geometry
publication date: 2013-04-29T00:00:00Z
review text: The authors present improved algorithms in order to find the maximum overlap of two polygonal shapes under translation and rigid motion, respectively. They improve the previous best running times by \textit{O. Cheong} et al. [Discrete Comput. Geom. 37, No. 4, 545--563 (2007; Zbl 1118.52011)] from \(\tilde O(n^2\varepsilon^{-4})\) to \(\tilde O(n^2\varepsilon^{-3})\) in the translation case, and from \(\tilde O(n^2\varepsilon^{-8})\) to \(\tilde O(n^2\varepsilon^{-4})\) in the rigid motion case. The same error bound holds with probability \(1-n^{-O(1)}\).
Mathematics Subject Classification ID: 65D18
zbMATH DE Number: 6159330
zbMATH Keywords: shape matching
zbMATH Keywords: overlap
zbMATH Keywords: random sampling
zbMATH Keywords: arrangement
zbMATH Keywords: algorithm
zbMATH Keywords: polygonal shape
zbMATH Keywords: error bound
reviewed by: Costică Moroşanu
MaRDI profile type: Publication
full work available at URL: j.comgeo.2013.01.002
OpenAlex ID: W2021810285
cites work: Maximum Overlap of Convex Polytopes under Translation
cites work: Maximizing the overlap of two planar convex sets under rigid motions
cites work: Q4038728
cites work: Probabilistic matching of planar regions
cites work: On the number of cells defined by a family of polynomials on a variety
cites work: Finding a guard that sees most and a shop that sells most
cites work: Algorithm Theory - SWAT 2004
cites work: Computing the maximum overlap of two convex polygons under translations
cites work: Q4038707
cites work: Q3772828
cites work: Dynamic Trees and Dynamic Point Location
cites work: Relative \((p,\varepsilon )\)-approximations in geometry
cites work: Improved bounds on the sample complexity of learning
cites work: On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
cites work: Q5417676
DOI: 10.1016/J.COMGEO.2013.01.002
Recommended article: Q4412893
Recommended article: A Dynamical Systems Approach for the Shape Matching of Polytopes Along Rigid-Body Motions
Recommended article: Shape Matching for Rigid Objects by Aligning Sequences Based on Boundary Change Points
Recommended article: Matching with Shape Contexts
description: scientific article; zbMATH DE number 6159330