Die Berechnung der Ähnlichkeit zweier geometrischer Figuren ist eine der fundamentalen Aufgaben der algorithmischen Geometrie. In der Regel wird die Ähnlichkeit durch eine reellwertige Abstandsfunktion gemessen. Im Laufe der Zeit sind einige solcher Abstandsfunktionen entwickelt worden, die auf unterschiedlichen Klassen von geometrischen Figuren definiert sind und jeweils verschiedene Aspekte der Ähnlichkeit bewerten. Die bisherigen Algorithmen zur Berechnung dieser Abstandsfunktionen setzen voraus, dass die geometrischen Figuren exakt gegeben sind. Diese Exaktheit ist in den meisten Anwendungen allerdings nicht gegeben, da die Eingabedaten durch Messungen gewonnen werden, die eine bestimmte Ungenauigkeit aufweisen. In vielen Fällen ist die mit der Messung verbundene Ungenauigkeit jedoch bekannt. Zwei wichtige Abstandsmaße zur Bestimmung der Ähnlichkeit geometrischer Formen sind der auf Punktmengen definierte gerichtete und ungerichtete Hausdorff-Abstand sowie der diskrete Fréchet-Abstand, der auf Punktfolgen definiert ist.

Im Rahmen der Dissertation wurden Algorithmen zur Berechnung dieser Abstandsmaße entwickelt, die die bekannten Ungenauigkeiten der Eingabedaten berücksichtigen, um das Supremum und Infimum des Ähnlichkeitswertes unter den im Rahmen der Ungenauigkeiten möglichen Ausprägungen der geometrischen Figuren exakt zu berechnen. Des Weiteren wurde bewiesen, dass in einigen Fällen die Berechnung des Infimums sowie seine Approximation mit einem bestimmten Approximationsfaktor NP-schwer ist. Für einige dieser Fälle wurden Approximationsalgorithmen entwickelt, die zum Teil die theoretisch bestmögliche Approximation erreichen. Die genannten Ergebnisse stellen einen Schwerpunkt der Dissertation dar und werden in diesem Vortrag vorgestellt.

Des Weiteren wird in dem Vortrag kurz auf die weiteren in der Dissertation enthaltenen Ergebnisse eingegangen. Hierzu zählen unter anderem Suchreduktionen, die eine nicht heuristische Nächste-Nachbar-Suche von Punktmustern ermöglichen, sowie die Beantwortung der zuvor offenen Frage, ob jedes Arrangement von n Geraden durch ein einfaches n-Gon induziert werden kann. In der Literatur gibt es viele nicht heuristische Suchstrukturen für einzelne Punkte sowie Suchheuristiken, um geometrische Muster zu suchen, die komplexer als ein einzelner Punkt sind. Die in der Dissertation vorgestellten Suchreduktionen ermöglichen die Reduktion von Suchen nach Punktmustern unter Abstandsmaßen, die nicht die Eigenschaften einer Metrik aufweisen müssen, auf Nächste-Nachbar-Suchen einzelner Punkte durch Einbettung in einen metrischen Raum. Für einige Abstandsmaße kann die benutzte Einbettung so erweitert werden, dass die Suchreduktion zu translationsinvarianten Suchen führt. Für die meisten betrachteten Abstandsmaße ermöglicht die Suchreduktion erstmals eine nicht heuristische Nächste-Nachbar-Suche unter diesem Abstandsmaß.