Detailseite
Projekt
Effiziente Repräsentation von geometrischer Ähnlichkeit
Antragstellerin
Professorin Dr. Anne Driemel
Fachliche Zuordnung
Theoretische Informatik
Förderung
Förderung seit 2022
Projektkennung
Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 459420781
Algorithmen in der Geodäsie müssen oft bestimmen können, ob sich zwei geometrische Objekte ähnlich oder unähnlich sind. Je nach Anwendung, benötigt der Algorithmus eine Definition dieser Ähnlichkeit, welche normalerweise in der Form eines mathematischen Abstandsmaßes gegeben wird.Allgemein gesprochen soll es in diesem Brückenprojekt auf zwei Ebenen um die mathematische Struktur und Komplexität der für die Forschungsgruppe relevanten Abstandsmaße gehen: (1) auf der Ebene des Abstands zweier individueller Objekte --- durch die Analyse der Berechnungskomplexität des Abstandsmaßes, und (2) auf der Ebene des gesamten metrischen Raumes --- durch die Analyse der VC-Dimension des dazugehörigen Mengensystems von metrischen Kugeln.Wir werden Varianten der Hausdorff und der Fréchet Metrik untersuchen. Diese Abstandsmaße werden in enger Zusammenarbeit mit Experten der Geodäsie der Projekte C1 und C2, und mit Experten der Algorithmen der Projekte A1,A2, A3, und B2 auf die Probleme der Forschungsgruppe zugeschnitten. Dies garantiert, dass die Abstandsmaße einerseits für die Anwendung geeignet sind, und andererseits auch effizient berechenbar sind. Somit ist dieses Projekt eng in die Zusammenarbeit der einzelnen Projekte innerhalb der gesamten Forschungsgruppe integriert. Ein weiteres Ziel des Projekts ist die Entwicklung und Analyse neuer algorithmischer Methoden für das Clustering, die Aggregation und die Vereinfachung von Polygonzügen und polygonalen Flächen. Die neuen Methoden sollten gleichermaßen auf die kartografische Generalisierung und auf das Clustering von ozeanische Sensordaten anwendbar sein. In beiden Fällen muss der Algorithmus eine kompakte geometrische Repräsentation finden, welche die definierte Ähnlichkeit zu den gemessenen Daten maximiert. Um eine möglichst breite Anwendbarkeit zu erreichen, werden wir die Probleme des Clustering und der Aggregation, die sich aus der Forschungsgruppe ergeben, in ihrer grundlegenden Form als Geometric Set Cover Probleme betrachten.
DFG-Verfahren
Forschungsgruppen
