FWF - Computational geometry - Industrial Geometry

Computational Geometry is dedicated to the algorithmic study of elementary geometric questions. Traditionally it deals with basic geometric objects like points, lines, and planes. For real world applications, however, often reliable techniques for advanced geometric primitives like surfaces and location query structures are needed. The role of this project is twofold. On one hand it will provide the theoretical background for advanced geometric algorithms and data structures for several other projects within this joint research project (JRP). These include geometric structures for fast information retrieval, the generation and manipulation of triangular meshes, the computation of suitable distance functions to multidimensional objects, and the representation of advanced geometric objects. Another aim of this project is to develop novel techniques for the manipulation and optimization of geometric structures. Here the emphasis is on geometric graphs (triangulation-like and Voronoi diagram-like structures, spanning trees). Properties of these structures will be investigated, with the goal of designing more efficient geometric algorithms and data structures. Existing geometric algorithms libraries (CGAL, LEDA) will be used to guarantee robustness of the developed algorithms.