Ph.D. thesis : Geometrische Mustererkennung in höheren Dimensionen

Carola Wenk

Advisor: Prof. Dr. Helmut Alt

Seien A und B zwei triangulierte Flächen im Raum. Wie ähnlich sind sich A und B? Als erstes muß ein Abstandsmaß gewählt werden. Dabei kommt die Fréchet-Metrik nicht in Frage, da, wie Michael Godau in seiner Dissertation gezeigt hat, schon das Entscheidungsproblem NP-schwer ist. Deshalb betrachten wir zunächst den Hausdorff-Abstand, der für n = max (|A|,|B|) in O(n³log³ n) berechnet werden kann.

In der Regel soll es aber erlaubt sein, aus einer Menge von Abbildungen, z.B. Translationen, diejenige herauszusuchen, die den Hausdorff-Abstand minimiert. Eine derartige Problemstellung gestaltet sich in höheren Dimensionen, d.h. in Dimensionen > 3, weitaus schwieriger. Betrachten wir das Entscheidungsproblem, ob es für ein gegebenes e eine Translation t gibt, so daß der gerichtete Hausdorff-Abstand d_H(A+t,B) <= e ist.

...

Von theoretischem Interesse ist es nun herauszufinden, ob es doch eine Möglichkeit gibt, weniger grobe Abschätzungen zu verwenden. So wurde in einer neuen Arbeit von Agarwal und Sharir für Strecken und sich nicht überschneidende Dreiecke im R³ unter Verwendung der euklidischen Metrik gezeigt, daß Be eine Komplexität von O(n^2+d) für beliebiges d > 0 hat, was fast der Vermutung O(n²) entspricht. Weiterhin sind auch andere Klassen von Abbildungen, wie z.B. starre Bewegungen, von Interesse, jedoch aufgrund der vielen Freiheitsgrade gerade in höheren Dimensionen schwierig zu handhaben. Für die Praxis stellt sich die Frage nach Approximationsmöglichkeiten oder einfacheren Spezialfällen, in denen die Laufzeit der Algorithmen überschaubarer ist.