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-51954
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 
fb14_1990_21.pdf13,08 MBAdobe PDFView/Open

Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.