Abstract
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 Õ(n²ε^-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 Õ(n³ε^-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 ε.