deutsch
|
MISSION STATEMENT:Theoretical Computer Science/Computational Geometry at the Institute of Simulation and GraphicsThe research group Computational Geometry works on the design and analysis of efficient algorithms for solving geometric problems. Recent research topics have been proximity problems, network problems for point sets, geometric optimization problems and data structures for basic geometric intersection problems. Most of our recent work has been of theoretic nature, with the exception of an implementation of parametric search and some algorithms solving proximity problems. Currently, we are working on the following topics. 1. Geometric Network ProblemsThe general problem can be formulated as follows. Given a set of points and obstacles, construct a "good" network connecting these points so that no edge intersects any obstacle. Although this is a classical problem, there are still many interesting problems to be solved. An example of a good network is the so-called spanner. Here, the aim is to construct a graph having the following property: Between every pair of points there is a path within the network whose length is at least a bit larger than the length of the shortest way way between both points. If this graph only contains a "few" edges, then it forms a good approximation for the complete Euclidean graph. These spanners are useful for motion planning problems occurring in robotics. It is our aim to design and implement efficient and practical algorithms for constructing those networks. Furthermore, we want to design and implement efficient algorithms for computing short paths in these graphs.2. Geometric Optimization Problems for Rapid Prototyping and ManufacturingThe emerging field of Rapid Prototyping and Manufacturing gives rise to several geometric optimization problems. A basic problem is the design of algorithms for solving the following problem. We are given a CAD model of an object, and would like to build a prototype using Layered Manufacturing. This technique uses a laser to build the prototype layer-by-layer. As a new layer may overhang the previous one, supports are used. At the end of the process, these supports are removed. The amount of supports (and the building time) depends on the orientation of the object. Therefore, algorithms have to be designed to compute the best direction or an approximation to it. In practice, heuristics are used to approximate the best possible direction; however, it is not clear, how good these heuristics are. We have designed some algorithms that solve some special versions of this problem. Unfortunately, these algorithms are too complicated to be relevant in practice. Currently, we are trying to design more practical algorithms.
Stefan Schirra
|
