Approximate algorithms for approximate congruence

Abstract

We study the decision problem whether two sets of n points in the plane are approximately congruent with a given tolerance \varepsilon. Approximate algorithm means that the algorithm is not guaranteed to take a decision for all tolerance values. For point sets A and B let \varepsilon_{opt}(A,B) be the smallest tolerance value premitting approximate congruence of A and B. An algorithm for approximate congruence is said to be (\alpha,\beta)-approximate for \alpha,\beta\geq0 if the algorithm is guaranted to give an answer for test values outside the interval [\varepsilon_{opt}(A,B)-\alpha,\varepsilon_{opt}(A,B)+\beta). For tolerance values in [\varepsilon_{opt}(A,B)-\alpha,\varepsilon_{opt}(A,B)+\beta), the algorithm may give an correct answer or may report that an answer cannot be found. We give an (\frac{1}{2}\varepsilon_{opt}(A,B),\varepsilon_{opt}(A,B))-approximate algorithm with time complexity O(n^{4}). We use an additional input parameter \gamma for tradeoff between running time and size of the uncertainty interval and give an (\gamma,\gamma)-approximate algorithm with running time O((\frac{\varepsilon}{\gamma})^{2}n^{4}). Moreover we give an (\frac{1}{2}\varepsilon_{opt}^{T}(A,B),\varepsilon_{opt}^{T}(A,B))-approximate algorithm with run time O(n^{2.5}) for approximate congruence enabled by a translation and an (\gamma,\gamma)-approximate algorithm for this case with running time O((\frac{\varepsilon}{\gamma})^{2}n^{2.5}). Here \varepsilon_{opt}^{T}(A,B) is the smallest tolerance value permitting approximate congruence of A and B enabled by a translation.