Navigation/Menü: Links auf weitere Seiten dieser Website
Objekt-Metadaten
| On the Computability of the Frechet Distance Between Triangulated Surfaces Buchin, Maike Elisabeth |
| Haupttitel | On the Computability of the Frechet Distance Between Triangulated Surfaces |
| Titelvariante | Über die Berechenbarkeit des Frechet-Abstands zwischen triangulierten Flächen |
| Autor | Buchin, Maike Elisabeth
Geburtsort: Hamburg, Deutschland |
| Gutachter | Prof. Dr. Helmut Alt |
| weitere Gutachter | Prof. Dr. Gert Vegter |
| Freie Schlagwörter | Computational Geometry, Computational Topology, Shape Matching, Frechet DistanceF.2.268Q25 |
| DDC | 004 Datenverarbeitung; Informatik |
| Zusammenfassung | 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. |
| Dokumente |
FUDISS_derivate_000000002618
Falls Ihr Browser eine Datei nicht öffnen kann, die Datei zuerst herunterladen und dann öffnen.
|
| Fachbereich/Einrichtung | FB Mathematik und Informatik |
| Erscheinungsjahr | 2007 |
| Dokumententyp/-Sammlungen | Dissertation |
| Medientyp/Format | Text |
| Sprache | Englisch |
| Rechte | Nutzungsbedingungen |
| Tag der Disputation | 23.04.2007 |
| Erstellt am | 30.07.2007 - 00:00:00 |
| Letzte Änderung | 19.02.2010 - 14:11:35 |
| Alte Darwin URL | http://www.diss.fu-berlin.de/2007/529/ |
| Statische URL | http://www.diss.fu-berlin.de/diss/receive/FUDISS_thesis_000000002618 |
| URN | urn:nbn:de:kobv:188-fudissthesis000000002618-3 |
| Zugriffsstatistik | |
