On distance measures for polygonal curves bridging between Hausdorff and Fréchet distance

Hausdorff- und Fréchet-Abstand sind häufig genutzte Ähnlichkeitsmaße. Für Kurven, insbesondere Polygonzüge, können beide Distanzmaße effizient berechnet werden. In dieser Arbeit werden neue Ähnlichkeitsmaße (\(\it Schnittdistanz\) und \(\it Überdeckungsdistanz\), englisch \(\textit {cut distance}\) und \(\textit {cover distance}\)) eingeführt, welche sowohl mit Fréchet- als auch mit Hausdorff-Abstand verwandt sind. Ein zusätzliches Ähnlichkeitsmaß (\(\it Stationendistanz\), englisch \(\textit {station distance}\)) wird als Vereinfachung der Schnittdistanz vorgestellt. Das Entscheidungsproblem aller vorgestellten Ähnlichkeitsmaße ist NP-schwer, es werden aber algorithmische Ansätze wie Approximations- und FPT-Algorithmen vorgestellt. Das Free \(\it Space-Diagramm\) ist das wichtigste Werkzeug zur Berechnung des Fréchet-Abstands, und das in dieser Arbeit untersuchte \(\textit {Free Space-Realisierungsproblem}\) (englisch \(\textit {free space realizability problem}\)) stellt die Frage, ob eine gegebene Konfiguration mit dem Free Space-Diagramm eines Paars von Kurven übereinstimmt.Hausdorff and Fréchet distance are popular means to compare point sets, curves, and higher dimensional objects. We introduce the \(\textit {cut distance}\) and the \(\textit {cover distance}\), which bridge between Hausdorff and Fréchet distance. As a variant of the cut distance, we also introduce the \(\textit {station distance}\). All novel distance measures are NP-hard to decide, but next to these reductions we present different algorithmic approaches such as approximation and FPT-algorithms for computing our distance measures. The free space and corresponding free space diagram is a key concept to efficiently computing the Fréchet distance and its variants. We study the free \(\textit {free space realizability problem}\), i.e., we ask whether there exists a pair of curves such that their corresponding free space diagram resembles a given (potential) free space configuration. It is NP-hard to maximize the number of realized cells in a given diagram, but we also give algorithms that decide realizability for certain input instances