Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen:
doi:10.22028/D291-26478
Titel: | Approximate algorithms for approximate congruence |
VerfasserIn: | Schirra, Stefan |
Sprache: | Englisch |
Erscheinungsjahr: | 1990 |
DDC-Sachgruppe: | 004 Informatik |
Dokumenttyp: | Forschungsbericht (Report zu Forschungsprojekten) |
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 zu diesem Datensatz: | urn:nbn:de:bsz:291-scidok-51954 hdl:20.500.11880/26534 http://dx.doi.org/10.22028/D291-26478 |
Schriftenreihe: | Technischer Bericht / A / Fachbereich Informatik, Universität des Saarlandes |
Band: | 1990/21 |
Datum des Eintrags: | 9-Apr-2013 |
Fakultät: | MI - Fakultät für Mathematik und Informatik |
Fachrichtung: | MI - Informatik |
Sammlung: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Dateien zu diesem Datensatz:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
fb14_1990_21.pdf | 13,08 MB | Adobe PDF | Öffnen/Anzeigen |
Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.