Project Details
Projekt
Efficient Representation of Geometric Similarity
Applicant
Professorin Dr. Anne Driemel
Subject Area
Theoretical Computer Science
Term
since 2022
Project identifier
Deutsche Forschungsgemeinschaft (DFG) - Project number 459420781
Algorithms in geodesy often need to determine if two geometric objects are similar or dissimilar. Depending on the specific application, the algorithm needs to be provided with a definition of this dissimilarity, which is usually done in the form of a mathematical distance measure.Broadly speaking, the aim of this bridge project is to study the mathematical structure and complexity of several distance measures relevant to this RU on two levels: (i) on the level of the distance between two individual objects via a study of the complexity of the distance computation, and (ii) on the level of the entire metric space via a study of the VC dimension of the corresponding set system of metric balls. We will explore adaptations of different geometric distance measures, such as the Fréchet distance and the Hausdorff distance, which are known to capture continuous geometries well. The distance measures are developed in close collaboration with the geodesy experts of projects C1 and C2 and algorithms experts of A1, A2, A3, and B2 to ensure (i) suitabilty to the application and (ii) efficient computability. In this way, the project is closely integrated into collaborations across the entire RU. The ultimate goal of the project is to study new algorithmic methods for clustering, aggregation and simplification involving polygonal curves and polygonal regions. The new methods should be applicable to cartographic generalization, as well as clustering of ocean remote sensing data. In both cases, the algorithm should find a compact representation of geometric objects which maximizes the similarity to the measured data points under an appropriate definition of geometric similarity. To achieve the goal of wide applicability, we study the clustering and aggregation problems that arise within this RU within the framework of geometric set cover formulations.
DFG Programme
Research Units
