Approximate decision algorithms for approximate congruence (Q1198006)

We derive a \(({1\over 2} \varepsilon_{opt}(A,B), \varepsilon_{opt}(A,B))\)-approximate algorithm for approximate congruence by translations with running time \(O(n^{2.5})\) and a \(({1\over 2},\varepsilon_{opt}(A,B) \varepsilon_{opt}(A,B))\)- approximate algorithm with running time \(O(n^ 4)\) for the general case. An additional input parameter \(\gamma\leq\varepsilon\) is used as tradeoff between running time and size of the indecision interval. We give a \((\gamma,\gamma)\)-approximate algorithm with running time \(O((\varepsilon/\gamma)^ 2 n^ 4)\) for the general case. The comparable (\((0,0)\)-approximate) algorithm of \textit{H. Alt}, \textit{K. Mehlhorn}, \textit{H. Wagener} and \textit{E. Welzl} [Congruence, similarity, and symmetries of geometric objects, Discrete Comput. Geom. 3, 237-256 (1988; Zbl 0679.68070)] has running time \(O(n^ 8)\). Furthermore we give a \((\gamma,\gamma)\)-approximate algorithm with running time \(O((\varepsilon/\gamma)^ 2 n^{2.5})\) for testing approximate congruence by translation. Here the comparable algorithm of H. Alt, K. Mehlhorn, H. Wagener and E. Welzl [loc. cit.] has running time \(O(n^ 6)\). Recently, \textit{P. J. Heffernan} [The translation square map and approximate congruence, Inform. Process. Lett. 39, 153-159 (1991; Zbl 0735.68084)] has given a \((\gamma,\gamma)\)-approximate algorithm with running time \(O((\varepsilon/\gamma)^ 6 n^ 3)\) for approximate congruence by translations.