The design and analysis of algorithms and data structures forms one of the core areas within computer science. The Algorithms chair (ALG) performs fundamental research in this area, focusing on algorithmic problems for spatial data. Such problems arise in geographic information systems (GIS) and automated cartography, robotics, computer graphics, CAD/CAM, and many other application areas.
Our research can be grouped into four closely related and partially overlapping areas:
This field combines clever algorithmic techniques with beautiful geometric concepts to obtain efficient solutions to algorithmic problems involving spatial data. Computational geometry can be seen as the fundamental study of algorithmic problems arising in the application areas mentioned above.
Modern computer systems have an increasingly complex memory architecture, organized hierarchically registers, several cache levels, main memory, and disk (or other external memory devices). An effective use of this memory hierarchy is often essential to obtain the best performance. Our research in this area focuses on algorithms with provable guarantees on their I/O- and caching behavior.
Networks play an important role in real life—think for example of road networks, computer networks, or social networks—and their mathematical counterpart, graphs, forms a central concept in computer science. To get more insight into a graph structure, it often helps to visualize it. The subarea within algorithms research studying the visualization of graphs is called graph drawing, and it is one of the focus areas of our group.
Algorithms for GIS and automated cartography
Spatial data play a central role in geographic information systems (GIS) and automated cartography, and there are many challenging algorithmic problems in these areas, often dealing with massive amounts of data. We apply our expertise in computational geometry and I/O-efficient algorithms to solve these problems in a rigorous way.
We offer thesis projects in all four areas. The exact topic of the thesis project is defined depending on the interest and skills of the students. Projects can range from purely theoretical projects to projects involving significant implementation and experimentation.
See for more information on the group and its projects on the website.