2009/02/25 by Helmut Alt, Alt, Helmut, Ludmila Scharf +3
Computer Science · #Computational Geometry (cs.CG) #FOS: Computer and information sciences #cs.CG
paper · pdf · doi:10.48550/arxiv.0902.4337
arxiv created 2009/02/25 · arxiv updated 2009/12/01
We analyze a probabilistic algorithm for matching shapes modeled by planar regions under translations and rigid motions (rotation and translation). Given shapes A and B, the algorithm computes a transformation t such that with high probability the area of overlap of t(A) and B is close to maximal. In the case of polygons, we give a time bound that does not depend significantly on the number of vertices.