DARWIN Digitale Dissertationen English Version Strich

FU Berlin
Digitale Dissertation

Michael Godau :
Über die Komplexität der Bestimmung der Ähnlichkeit von geometrischen Objekten in höheren Dimensionen
On the complexity of measuring the similarity between geometric objects in higher dimensions

 FU Logo

|Zusammenfassung| |Inhaltsverzeichnis| |Ergänzende Angaben|

Zusammenfassung

In der Mustererkennung und der Qualitätskontrolle ist der Vergleich geometrischer Objekte ein oft betrachtetes Problem. Um die Ähnlichkeit zwischen Objekten in Zahlen zu fassen, ist es ein natürlicher Ansatz, diese als Elemente eines metrischen Raumes aufzufassen und den Grad ihrer Ähnlichkeit als den Abstand zwischen ihnen.

Die geometrischen Objekte, die hier betrachtet werden, sind Kurven, Flächen oder Analoga in höheren Dimensionen, welche für gewöhnlich als Äquivalenzklassen parametrisierter Kurven, parametrisierter Flächen und so weiter betrachtet werden. Wir nehmen an, daß diese Objekte durch eine endliche Struktur beschrieben werden. Das bedeutet für Kurven, daß sie aus endlich vielen Strecken bestehen, für Flächen, daß sie aus endlich vielen Dreiecken bestehen usw.

Eine natürliche Metrik, welche die Ähnlichkeit zwischen ihnen ausdrückt, ist die Fréchetmetrik, zuerst erwähnt 1906. Speziell in der Variationsrechnung ist dies die dort betrachtete Standardmetrik.

Algorithmen für stückweise affine Kurven wurden bereits in anderen Arbeiten untersucht. Die darin für die Abstandsmessung solcher Kurven gegebenen Algorithmen hatten polynomiale Laufzeiten geringer Laufzeit.

In höheren Dimensionen ist nicht einmal bekannt, ob ein Polynomialzeitalgorithmus existiert. Unter anderem wird in dieser Arbeit gezeigt, daß das Problem NP-schwer ist für höhere Dimensionen. Als Nebenergebnis dieser Forschung wird ein weiteres NP-Schwerheitsergebnis aus dem Gebiet des Graphenzeichnens bewiesen.

Auf der Suche nach einem effizienteren Weg, den Abstand zwischen solchen Objekten zu berechnen, wird ferner die wohlbekannte Hausdorffmetrik untersucht. Für diese Metrik werden Polynomialzeitalgorithmen für jede Dimension angegeben und bewiesen, daß diese Metrik für konvexe Objekte mit der Fréchetmetrik übereinstimmt.

Inhaltsverzeichnis

Die gesamte Dissertation können Sie als gezippten tar-File oder als zip-File laden.

Durch Anklicken der Kapitelüberschriften können Sie das Kapitel in PDF-Format laden:

Cover and Contents
1 Introduction .......3
1.1 Overview .......3
1.2 How to read this thesis .......4
1.3 Credits .......4
2 The Hausdorff metric .......5
2.1 Definition .......5
2.2 Drawbacks .......5
2.3 Simplicial complexes .......6
2.4 Algorithms .......6
2.5 Framework .......7
2.6 Brute force .......8
2.7 Using the structure of the lower envelope .......17
3 The Fréchet Metric .......19
3.1 Motivation .......19
3.2 Definitions .......19
3.3 Previous work .......21
3.4 The main theorem .......21
3.5 Background .......21
3.6 The selection problem .......25
3.7 Back to the Fréchet metric .......33
3.8 The gadget .......33
3.9 The reduction .......39
3.10 How the gadgets work .......40
3.11 How the gadgets do not work .......48
3.12 Remarks .......55
3.13 Open problems .......55
4 The connection between the Hausdorff and the Fréchet metric .......57
5 A related problem .......61
5.1 Introduction .......61
5.2 The Reduction .......62
5.3 Open problems .......70
A Drawings on large scale .......71
B Zusammenfassung .......79
C Lebenslauf .......81
Bibliography .......83

Ergänzende Angaben:

Online-Adresse: http://www.diss.fu-berlin.de/1999/1/index.html
Sprache: Englisch
Keywords: computational geometry; pattern matching; Fréchet metric; NP; graph drawing
DNB-Sachgruppe: 27 Mathematik
Klassifikation MSC: 68Q15
Klassifikation CR: F.2.m
Datum der Disputation: 18-Dec-1998
Entstanden am: Fachbereich Mathematik u. Informatik, Freie Universität Berlin
Erster Gutachter: Prof. Dr. Helmut Alt
Zweiter Gutachter: Prof. Dr. Günter Ziegler
Kontakt (Verfasser): godau@math.fu-berlin.de
Kontakt (Betreuer): alt@inf.fu-berlin.de
Abgabedatum:13-Jan-1999
Freigabedatum:13-Jan-1999

 

|| DARWIN|| Digitale Dissertationen || Dissertation|| English Version|| FU Berlin|| Seitenanfang ||

Mail-Icon Fragen und Kommentare an:
darwin@inf.fu-berlin.de

© Freie Universität Berlin 1999