Geometric Algorithms

Contact: Marc van Kreveld

We live in a three-dimensional world. Not surprisingly therefore, in many domains of computer science it is necessary to store, analyze, and create or manipulate spatial data. These domains have their own characteristics, but they also share many underlying concepts and there are several techniques that are applicable in a number of different domains. The field of computational geometry studies these fundamental concepts and techniques. It is an exciting field that combines clever algorithmic techniques and beautiful geometric structures to obtain general techniques for the efficient storage and processing of spatial data. Implementation issues related to geometric computing, for instance how to deal with the finite precision in actual implementations, and how to handle degenerate configurations, play an increasingly important role.

We perform fundamental research on computational geometry, but we also apply tools from this field to develop geometric algorithms and data structures for various application areas. For instance, we have ample experience in solving algorithmic problems arising in Geographic Information Systems (GIS), such as map generalization and label placement. In the area of robotics we work on manufacturing problems, robot path planning, and collision avoidance. In all these areas, the geometric problems are solved in a rigorous way, resulting in solutions with provable properties and guaranteed efficiency.

The research in the group focuses on the following topics:

Computational Geometry
Computational geometry is the area within algorithms research dealing with geometric problems. Our research group has a long-standing tradition in this area, and is one of the largest groups in the world working on it. We study both `pure' computational-geometry problems, as well as fundamental aspects of problems arising in application areas. Although our work in the latter category is fundamental, we keep the applications in mind. For instance, we try to formalize and use the characteristics of the geometry in the application in the analysis of our solutions. This should lead to algorithms and data structures that are provably efficient in practical situations.

Automated Cartography and GIS
In Geographic Information Systems (GIS) a lot of cartographic and geographic data is available in geometric form. These systems store highly detailed information so that large-scale topographic maps can be produced with high quality. However, from this data it should also be possible to produce maps at smaller scales, which requires cartographic generalization. This is a geometric transformation that can be automated using sophisticated methods. Other cartographic tasks that can be automated are text placement and statistical mapping. Animated and interactive maps offer even more possibilities for visualization. In GIS our research focuses on geographic information retrieval.

webmaster: Geert-Jan Giezeman