Shape matching under rigid motion (Q1947970)

The authors present improved algorithms in order to find the maximum overlap of two polygonal shapes under translation and rigid motion, respectively. They improve the previous best running times by \textit{O. Cheong} et al. [Discrete Comput. Geom. 37, No. 4, 545--563 (2007; Zbl 1118.52011)] from \(\tilde O(n^2\varepsilon^{-4})\) to \(\tilde O(n^2\varepsilon^{-3})\) in the translation case, and from \(\tilde O(n^2\varepsilon^{-8})\) to \(\tilde O(n^2\varepsilon^{-4})\) in the rigid motion case. The same error bound holds with probability \(1-n^{-O(1)}\).