FU Berlin Digitale Dissertation
Michael Godau : On the complexity of measuring the similarity between geometric objects in higher dimensions Über die Komplexität der Bestimmung der Ähnlichkeit von geometrischen Objekten in höheren Dimensionen
|Abstract| |Table of Contents| |More Information|

Abstract In pattern recognition and quality control the comparison of geometric objects is an often considered problem. In order to quantify the similarity between geometric objects a natural approach is considering them as elements of some metric space and evaluating their degree of similarity by simply computing the distance between them. The geometric objects we consider in this thesis are curves, surfaces or analogues in higher dimensions usually seen as equivalence classes of parameterized curves, parameterized surfaces and so on. We assume the objects to be described by a finite structure. That means for curves that they consist of finitely many line segments and for surfaces that they consist of triangles and so on. A natural metric defining the similarity between them is the Fréchet distance, first described in 1906. Especially in the calculus of variations this is the standard metric considered. Algorithms for piecewise affine curves already have been investigated in different publications. The given algorithms for computing the distance between such curves have had a polynomial runtime of low degree. In higher dimensions it is not known whether there exists even a polynomial time algorithm. However, among other things, in this thesis it will be shown that the problem is NP-hard for higher dimensions. As a byproduct of this research we also prove some NP-hardness result in graph drawing. In search for a more efficient way to calculate the distance between those objects we investigate the well known Hausdorff metric as well. For this metric we give polynomial time algorithms for any dimension and we prove that for convex objects this metric coincides with the Fréchet metric.

Table of Contents Download the whole PhDthesis as a zip-tar file or as zip-File For download in PDF format click the chapter title 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

More Information:
Online available:	http://www.diss.fu-berlin.de/1999/1/indexe.html
Language of PhDThesis:	english
Keywords:	computational geometry; pattern matching; Fréchet metric; NP; graph drawing
DNB-Sachgruppe:	27 Mathematik
Classification MSC:	68Q15
Classification CR:	F.2.m
Date of disputation:	18-Dec-1998
PhDThesis from:	Fachbereich Mathematik u. Informatik, Freie Universität Berlin
First Referee:	Prof. Dr. Helmut Alt
Second Referee:	Prof. Dr. Günter Ziegler
Contact (Author):	godau@math.fu-berlin.de
Contact (Advisor):	alt@inf.fu-berlin.de
Date created:	13-Jan-1999
Date available:	13-Jan-1999

 

---

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

---

	Fragen und Kommentare an: darwin@inf.fu-berlin.de
© Freie Universität Berlin 1999