Algorithms

Computational geometry
Computational geometry is the field within algorithms research dealing with the design and analysis of algorithms and data structures for spatial data. 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. As such, it forms the core of our research program.

I/O-efficient algorithms
Modern computer systems have an increasingly complex memory architecture, where memory is organized hierarchically into layers of increasing size but decreasing speed: 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.

Graph drawing
Networks play an important role in real life-think for example of road networks, computer networks, or social networks-and it is therefore not surprising that 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. It has many applications, including in GIS and automated cartography, and is one of the focus areas of our group.

Algorithms for GIS and automated cartography
Spatial data plays 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.

Parameterized complexity
Parameterized or multivariate algorithmics is a rigorous toolset to deal with computational problems that have multiple natural parameters. The goal is to give more efficient and finely tuned algorithms that are able to turn small parameter values to its advantage, resulting in better running times. Providing better algorithms and finding complexity bounds gives a much needed insight into many computationally hard problems that would be unreachable by the standard toolset: it helps us find the relevant structural parameters. An important subfield is kernelization, where one intends to provide preprocessing algorithms that reduce the input to a smaller equivalent instance, which is therefore more tractable.