Bewertung der Ähnlichkeit von geometrischen Graphen

In der algorithmischen Geometrie wurde das Anpassungsproblem für geometrische Muster vom theoretischen Standpunkt aus untersucht. Dabei wurden effiziente Algorithmen entwickelt, die die Ähnlichkeit von geometrischen Objekten messen; zwei solche Objekte betrachtet man als ähnlich, wenn sich ihre Geometrie nicht wesentlich unterscheidet.

Ziel des Projekts ist es, diese Ideen für den Fall zu verallgemeinern, bei dem die Muster durch geometrische Graphen (d.h. planare Graphen mit einer kreuzungsfreien Zeichnung in der Ebene) repräsentiert werden. Dazu muss nicht nur die Geometrie der Muster (Graphen) berücksichtigt werden, sondern auch ihre topologische und kombinatorische Struktur. Dieses Ähnlichkeitsmodell ist für viele praktische Probleme der Mustererkennung besser geeignet als ein rein geometrisches Modell, wie etwa für die Erkennung von Ägyptischen Hieroglyphen, chinesischen Schrifzeichen, oder elektronischen Komponenten in einem Schaltkreisdiagram.

Im Lauf des Projekts soll zunächst ein geeigneter Abstandsbegriffs für geometrische Graphen gefunden werden. Weiterhin sollen asymptotisch effiziente Algorithmen entwickelt werden, um die Ähnlichkeit von geometrischen Graphen zu messen. Längerfristig ist es das Ziel, eine effiziente Datenstruktur zu entwerfen, mit der aus einer grossen Menge von Graphen derjenige schnell bestimmt werden kann, der zu einem gegebenen Anfragegraphen am Ähnlichsten ist.

Dieses Projekt wird in Kooperation mit Prof. Otfried Cheong vom Korea Advanced Institute of Science and Technology (KAIST) in Daejeon, Südkorea durchgeführt.