Shape matching under rigid motion
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)}\).
scientific article; zbMATH DE number 6159330
scientific article