Algorithm Engineering for Geometric Graphs

几何图的算法工程

• 批准号: 498605127
• 负责人: Professorin Dr. Petra Mutzel
• 金额: --
• 依托单位: Informatik 1: Computational Analytics
• 依托单位国家: 德国
• 项目类别: Research Units
• 资助国家: 德国
• 项目状态: 未结题
• 来源: https://gepris.dfg.de/gepris/projekt/498605127?language=en
• 关键词: Algorithm; Engineering; Geometric; Graphs

Within our RU graphs appear directly as cartographic maps or indirectly as their geometric dual graphs, as shortcut graphs or as triangulations. Within this project, we will consider these structures as geometric graphs, i.e. graphs embedded on the plane (or on a surface). These graphs are often sparse, even planar, and thus allow for more efficient graph algorithms than general graphs. We will develop algorithmic engineering approaches for practically solving discrete optimization problems on geometric graphs related to the clustering, aggregation, and simplification problems that occur within our RU. An important goal is to speed up and to improve the quality of combinatorial as well as integer-linear-programming approaches for discrete (multi-objective) optimization problems on geometric graphs. This will be achieved by carefully taking the graph topology and the (geometric) structure of the given input data into account, sometimes in combination with learning approaches. For some of these problems, new similarity measures for geometric graphs, which we will develop jointly with B1, will play an important role. Another important ingredient are carefully engineered data structures to support queries about graphs and interactive maps.As a bridge project, jointly with B1, we will make sure that the theoretical concepts and algorithms suggested in projects A1, A2, and A3 will find a suitable realization in the geodesy projects C1 and C2. Our work program is closely interlinked with all the other subprojects.

在我们的RU图中，直接作为制图地图或间接作为其几何对偶图、快捷图或三角剖分图出现。在这个项目中，我们将这些结构视为几何图形，即嵌入平面（或曲面）上的图形。这些图通常是稀疏的，甚至是平面的，因此允许比一般图更有效的图算法。我们将开发算法工程方法，用于实际解决与我们RU内发生的聚类，聚合和简化问题相关的几何图形上的离散优化问题。一个重要的目标是加快和提高质量的组合以及整数线性规划方法的离散（多目标）优化问题的几何图形。这将通过仔细考虑给定输入数据的图形拓扑和（几何）结构来实现，有时与学习方法相结合。对于其中的一些问题，新的相似性措施的几何图形，我们将共同开发B1，将发挥重要作用。 另一个重要组成部分是精心设计的数据结构，以支持有关图形和交互式地图的查询。作为一个桥梁项目，我们将与B1联合确保项目A1、A2和A3中提出的理论概念和算法将在大地测量项目C1和C2中找到合适的实现。我们的工作计划与所有其他子项目密切相关。