Spacial Decompositions and Graphs

• Applicants: Professor Dr. Rolf Klein; Professor Dr. Günter Rote
• Subject Area: Theoretical Computer Science
• Term: from 2011 to 2015
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 195353115

Many theoretical and practical geometric problems lead to decompositions of space as part of their analysis or as part of their solution: The Voronoi diagram and its dual decomposition, the Delaunay tessellation is just the most classical and fundamental example. The underlying "space" can be the Euclidean ambient space that we live in, or some more abstract parameter space or for example the configuration space of a robot. On the one hand, there are many hard questions about the classical Voronoi diagrams that remain open (such as complexity of Voronoi diagrams of moving points). On the other hand, many spatial decompositions that can be considered as variations of Voronoi diagrams have recently emerged, for example decompositions defined by some converging process such as Newton's method for finding roots, or decompositions that are related to pattern matching problems. For these new structures, even some basic questions (like uniqueness, the basic structure of cells) have not been investigated. Four main structures will be investigated: (i) Voronoi diagrams, (ii) Skeletal structures, (iii) Variants of triangulations, and (iv) Proximity graphs.

• DFG Programme: Research Grants