Please use this identifier to cite or link to this item: `doi:10.22028/D291-26478 `
 Title: Approximate algorithms for approximate congruence Author(s): Schirra, Stefan Language: English Year of Publication: 1990 DDC notations: 004 Computer science, internet Publikation type: Report 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. Link to this record: urn:nbn:de:bsz:291-scidok-51954hdl:20.500.11880/26534http://dx.doi.org/10.22028/D291-26478 Series name: Technischer Bericht / A / Fachbereich Informatik, Universität des Saarlandes Series volume: 1990/21 Date of registration: 9-Apr-2013 Faculty: MI - Fakultät für Mathematik und Informatik Department: MI - Informatik Collections: SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Files for this record:
File Description SizeFormat