2013/04/18 by Edgar Chávez, Chávez, Edgar, Ana C. Chávez-Cáliz +3
Computer Science · #51N10 #Algorithms and Data Compression #Computational Geometry and Mesh Generation #Computer Vision and Pattern Recognition (cs.CV) #Data Management and Algorithms #FOS: Computer and information sciences #cs.CV #msc:51N10
paper · pdf · doi:10.48550/arxiv.1304.4994
arxiv created 2013/04/18 · openalex publication_date 2013/04/18 · arxiv updated 2013/04/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a collection \Z1,Z2,…,Zm\ of n-sided polygons in the plane and a query polygon W we give algorithms to find all Z_ℓ such that W=f(Z_ℓ) with f an unknown similarity transformation in time independent of the size of the collection. If f is a known affine transformation, we show how to find all Z_ℓ such that W=f(Z_ℓ) in O(n+log(m)) time. For a pair W,W^′ of polygons we can find all the pairs Z_ℓ,Zℓ^′ such that W=f(Z_ℓ) and W^′=f(Zℓ^′) for an unknown affine transformation f in O(m+n) time. For the case of triangles we also give bounds for the problem of matching triangles with variable vertices, which is equivalent to affine matching triangles in noisy conditions.