dc.contributor.author
Buchin, Maike Elisabeth
dc.date.accessioned
2018-06-07T15:59:58Z
dc.date.available
2007-07-30T00:00:00.649Z
dc.identifier.uri
https://refubium.fu-berlin.de/handle/fub188/1909
dc.identifier.uri
http://dx.doi.org/10.17169/refubium-6111
dc.description
Cover
Contents
Abstract, Zusammenfassung, Acknowledgements
1\. Introduction
1.1 Shape Matching
1.2 Frechet Distance
1.3 Overview of the Thesis
2\. Preliminaries
2.1 Curves and Surfaces
2.2 Hausdorff Distance
2.3 Frechet Distance
2.4 Model of Computation
3\. Semi-Computability
3.1 Introduction
3.2 Computability of Real-valued Functions
3.3 Approximating the Homeomorphisms
3.4 Discrete Frechet Distance
3.5 Semi-Computing the Frechet Distance
3.6 Discussion
4\. Weak Frechet Distance
4.1 Introduction
4.2 Weak Frechet Distance
4.3 Free Space Diagram of Triangulated Surface
4.4 Characterizing the Weak Frechet Distance
4.5 Deciding the Weak Frechet Distance
4.6 Computing the Weak Frechet Distance
4.7 Discussion
5\. Simple Polygons
5.1 Introduction
5.2 Simple Polygons
5.3 Restricting the Set of Homeomorphisms
5.4 Deciding the Frechet Distance
5.5 Computing the Frechet Distance
5.6 Discussion
6\. Summed and Average Frechet Distance
6.1 Introduction
6.2 Definitions
6.3 Relaxed Triangle-Inequality is not fulfilled
6.4 Discussion
Bibliography
Index
dc.description.abstract
The Frechet distance is a metric for parameterized curves and surfaces. It is
used in shape matching for measuring the similarity of geometric shapes. For
polygonal curves, it can be computed in polynomial time. For triangulated
surfaces, deciding whether the Frechet distance between two surfaces is less
than or equal a given threshold is NP-hard. It is not known, whether the
Frechet distance between triangulated surfaces is computable. In this thesis,
we study the computability of the Frechet distance between triangulated
surfaces. We give three partial answers to the question whether it is
computable. For triangulated surfaces, we show that the Frechet distance is
semi-computable, a weaker notion of computability. For a variant of the
Frechet distance, the weak Frechet distance, we show that it is polynomial
time computable for triangulated surfaces. For a restricted class of surfaces,
simple polygons, we show that the Frechet distance is polynomial time
computable. Finally, we study a related question, the definition of a summed
or average Frechet distance between curves. We show that none of several
intuitive definitions fulfill the triangle inequality.
de
dc.description.abstract
Der Frechet Abstand ist eine Metrik für parametrisierte Kurven und Flächen. Er
wird benutzt, um die Ähnlichkeit geometrischer Formen zu messen. Für
polygonale Kurven kann er in polynomieller Zeit berechnet werden. Für
triangulierte Flächen ist es NP-schwer zu entscheiden, ob der Frechet Abstand
zwischen zwei Flächen kleiner oder gleich einem gegebenen Wert ist. Es ist
nicht bekannt, ob der Frechet Abstand zwischen triangulierten Flächen
berechenbar ist. In dieser Arbeit wird die Berechenbarkeit des Frechet
Abstandes zwischen triangulierten Flächen untersucht. Wir geben drei
Teilantworten auf die Frage, ob dieser berechenbar ist. Für triangulierte
Flächen zeigen wir, dass der Frechet Abstand semi-berechenbar ist, eine
schwächere Form der Berechenbarkeit. Für eine Variante des Frechet Abstandes,
den schwachen Frechet Abstand, zeigen wir, dass er in polynomieller Zeit
berechenbar ist für triangulierte Flächen. Für eine eingeschränkte Klasse von
Flächen, einfache Polygone, zeigen wir, dass der Frechet Abstand in
polynomieller Zeit berechenbar ist. Schließlich betrachten wir eine verwandte
Fragestellung, die Definition eines summierten oder durchschnittlichen Frechet
Abstandes zwischen Kurven. Wir zeigen, dass mehrere intuitive Definitionen
nicht die Dreiecksungleichung erfüllen.
de
dc.rights.uri
http://www.fu-berlin.de/sites/refubium/rechtliches/Nutzungsbedingungen
dc.subject
Computational Geometry
dc.subject
Computational Topology
dc.subject
Shape Matching
dc.subject
Frechet Distance
dc.subject.ddc
000 Informatik, Informationswissenschaft, allgemeine Werke::000 Informatik, Wissen, Systeme::004 Datenverarbeitung; Informatik
dc.title
On the Computability of the Frechet Distance Between Triangulated Surfaces
dc.contributor.firstReferee
Prof. Dr. Helmut Alt
dc.contributor.furtherReferee
Prof. Dr. Gert Vegter
dc.date.accepted
2007-04-23
dc.date.embargoEnd
2007-07-05
dc.identifier.urn
urn:nbn:de:kobv:188-fudissthesis000000002618-3
dc.title.translated
Über die Berechenbarkeit des Frechet-Abstands zwischen triangulierten Flächen
de
refubium.affiliation
Mathematik und Informatik
de
refubium.mycore.fudocsId
FUDISS_thesis_000000002618
refubium.mycore.transfer
http://www.diss.fu-berlin.de/2007/529/
refubium.mycore.derivateId
FUDISS_derivate_000000002618
dcterms.accessRights.dnb
free
dcterms.accessRights.openaire
open access