Tudor Soroceanu

Implementierung eines Approximations-Algorithmus für die Berechnung der diskreten Fréchet-Metrik

Betreuer: Prof. Dr. Wolfgang Mulzer
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 19.05.2015

Kurzbeschreibung

Die Fréchet-Metrik ist ein weit verbreitetes und gut untersuchtes Maß zur Bestimmung der Ähnlichkeit zwischen Kurven. Es gibt mehrere Varianten dieser Metrik; der Schwerpunkt der Bachelorarbeit liegt auf der diskreten Fréchet-Metrik, welche die Eckpunkte von Polygonzügen betrachtet. Der initiale Algorithmus von Eiter und Mannila [1] hat eine Laufzeit von O(n^2). Erst kürzlich konnten leicht subquadratische Algorithmen dafür gefunden werden. Jedoch hat Bringmann [2] gezeigt, dass es unmöglich ist, für das Problem eine Lösung mit stark subquadratischer Laufzeit O(n^(2-e)), für ein konstantes e > 0, zu finden. Daraufhin sind Bringmann und Mulzer [3] der Frage nachgegangen, wie gut sich die Fréchet-Metrik approximieren lässt und haben zwei Approximationsalgorithmen dazu vorgestellt: Einen gierigen Algorithmus mit linearer Laufzeit, der eine Approximationsschranke von 2^O(n) hat und einen allgemeinen alpha-approximativen Algorithmus, der O(n \log n + (n^2) / alpha) Zeit benötigt, für jedes 1 <= alpha <= n. Im Rahmen der Bachelorarbeit wurden diese beiden Algorithmen und zwei Referenzalgorithmen implementiert und experimentell untersucht. Die Ergebnisse des gierigen Algorithmus sind weitaus besser, als es die Schranke von 2^O(n) vermuten lässt. Die Implementierung des alpha-Approximationsalgorithmus konnte in den Experimenten die gute theoretische Laufzeit jedoch nicht bestätigen.