We present improved algorithms to efficiently match two polygonal shapes. Let n be their total number of vertices. Our first algorithm finds a translation vector that approximately maximizes the overlap area of the two shapes under translation in Õ(n2ε-3) time. The error is additive and it is at most ε times the minimum of the area of the two shapes, with high probability, i.e. at least 1 - n-r, where r is any positive constant fixed a priori. We also obtain an algorithm that approximately maximizes the overlap under rigid motion in Õ(n3ε-4) time. The same error bound holds with high probability. These results compare favorably with previous results which have higher polynomial dependence on n or ε.
Permanent URL for this record: https://lbezone.hkust.edu.hk/bib/b1198608