Detailseite
Projekt Druckansicht

Spacial Decompositions and Graphs

Fachliche Zuordnung Theoretische Informatik
Förderung Förderung von 2011 bis 2015
Projektkennung Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 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-Verfahren Sachbeihilfen
 
 

Zusatzinformationen

Textvergrößerung und Kontrastanpassung