Ph.D. thesis : Algorithmen zur Ähnlichkeitsbestimmung zwischen geometrischen Objekten unter Verwendung der Fréchet-Metrik
Michael Godau
Advisor: Prof. Dr. Helmut Alt
Um die Ähnlichkeit zwischen Objekten auszudrücken, betrachtet man diese Objekte als Punkte in einem metrischen Raum und bezeichnet zwei Objekte als mehr oder weniger ähnlich, wenn sie sich als Punkte mehr oder weniger nahe sind. In diesem Sinne berechnen Algorithmen zur Ähnlichkeitsbestimmung nichts anderes als den Abstand der Objekte in einem geeignet definierten metrischen Raum.
Die geometrischen Objekte, um die es gehen wird, sind beispielsweise Kurven in der Ebene, Flächen im Raum, usw. Um dies einheitlich behandeln zu können, fassen wir die Objekte als Funktionen auf von einer n-dimensionalen Mannigfaltigkeit in einen metrischen Raum. Damit dies überhaupt algorithmisch faßbar wird, müssen wir natürlich davon ausgehen, daß die Objekte eine endliche Beschreibung besitzen. Daher nehmen wir ferner an, daß die n-dimensionale Mannigfaltigkeit ein n-dimensionaler simplizialer Komplex ist und daß die Funktion diesen auf den R ^m abbildet, dabei affin-linear auf jedem Simplex ist, und zwar mit rationalen Koordinaten auf den Eckpunkten des Simplex.
Gebräuchliche Abstandsmaße für diese Gebilde wären beispielsweise die Hausdorff- bzw. die Fréchet-Metrik. Die Hausdorffmetrik ist eigentlich ein Abstandsbegriff für Mengen von Punkten in einem metrischen Raum. Für Funktionen geeigneter ist eigenlich die Fréchet-Metrik. Was die algorithmischen Aspekte angeht, ist leider die Fréchet-Metrik sehr viel weniger weit theoretisch durchdrungen als die Hausdorffmetrik, deshalb soll sie Hauptgegenstand der Untersuchungen werden.
Der Fréchet-Abstand zwischen zwei Funktionen f: A -> V und g: B -> V ist definiert als das Infimum über alle orientierungserhaltenden Homöomorphismen h: A -> B von dem maximalen punktweisen Abstand zwischen f und g o h . Wir wollen A und B als kompakt und zusammenhängend voraussetzen. Sind nun A und B nicht homöomorph, so ist das Infimum nicht definiert bzw. unendlich. Ab d groessergleich 4 ist das Problem, ob zwei als simpliziale Komplexe gegebene d-dimensionale Mannigfaltigkeiten homöomorph sind, unentscheidbar. Das wirft ein Licht auf die Komplexität der damit zusammenhängenden Probleme. So ist denn auch ab Dimension vier nicht mehr zu erwarten, überhaupt einen Algorithmus zur Abstandsmessung bezüglich der Fréchet-Metrik zu finden. Für eindimensionale Gebilde hingegen, also (polygonale) Kurven, sind Algorithmen sogar polynomieller Laufzeit bekannt und werden auch in der Praxis angewendet.
Ab Dimension zwei ist nichts mehr bekannt, abgesehen davon, daß ich einen (noch unveröffentlichen) Beweis dafür gefunden habe, da allein das approximative Entscheidungsproblem für die Fréchet-Metrik bereits NP-schwer ist. Dies legt nahe, daß es keinen Algorithmus polynomieller Laufzeit geben kann, um die Fréchet-Metrik bis auf einen bestimmten konstanten relativen Fehler genau zu berechnen.