Organization profile

Introduction / mission

The design and analysis of algorithms and data structures forms one of the core areas within computer science. The Algorithms Group performs fundamental research in this area, focussing 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.

Highlighted phrase

The design and analysis of algorithms and data structures forms one of the core areas within computer science. 

Organisational profile

Our research can be grouped into five closely related and partially overlapping areas: 

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.

Fingerprint Dive into the research topics where Algorithms is active. These topic labels come from the works of this organisation's members. Together they form a unique fingerprint.

  • Network Recent external collaboration on country level. Dive into details by clicking on the dots.

    Research Output

    Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency: Proceedings of the 14th International Workshop on the Algorithmic Foundations of Robotics (WAFR 20)

    Afshani, P., de Berg, M. T., Buchin, K. A., Gao, J., Löffler, M., Nayyeri, A., Raichel, B., Sarkar, R., Wang, H. & Yang, H-T., 2020, 25 p. Cornell university.

    Research output: Other contributionAcademic

  • Characterizing width two for variants of treewidth

    Bodlaender, H. L., Kratsch, S., Kreuzen, V. J. C., Kwon, O-J. & Ok, S., 10 Jan 2017, In : Discrete Applied Mathematics. 216, Part 1, p. 29-46 18 p.

    Research output: Contribution to journalArticleAcademicpeer-review

  • 6 Citations (Scopus)
    2 Downloads (Pure)

    On structural parameterizations of hitting set: hitting paths in graphs using 2-SAT

    Jansen, B. M. P., 5 Aug 2016, Graph-Theoretic Concepts in Computer Science : 41st International Workshop, WG 2015, Garching, Germany, June 17-19, 2015. Mayr, E. W. (ed.). Berlin: Springer, p. 472-486 (Lecture Notes in Computer Science; vol. 9224).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    Open Access
  • 1 Citation (Scopus)
    57 Downloads (Pure)