Shape matching under rigid motion

We present improved algorithms to match two polygonal shapes P and Q to approximate their maximum overlap. Let n be their total number of vertices. Our first algorithm finds a translation that approximately maximizes the overlap area of P and Q   under translation in O˜(n2ε−3) time. The error is additive and it is at most ε⋅min{area(P),area(Q)}ε⋅min{area(P),area(Q)} with probability 1−n−O(1)1−n−O(1). We also obtain an algorithm that approximately maximizes the overlap of P and Q   under rigid motion in O˜(n3ε−4) time. The same error bound holds with probability 1−n−O(1)1−n−O(1). We also show how to improve the running time to O˜(n+ε−3) for the translation case when one of the polygons is convex.