Algorithms (ALG)

Group leader: prof.dr. M.T. de Berg

Mark de Berg received an M.Sc. in computer science from Utrecht University (the Netherlands) in 1988. He received a Ph.D. from the same university in 1992, after which he became a permanent faculty member. In 2002 he moved to the Eindhoven University of Technology, where he became a full professor and head of the TU/e Algorithms Group.

His research area is algorithms and data structures and, in particular, computational geometry. In 2003 he obtained a prestigious VICI grant for his research from the Netherlands Organization for Scientific Research (NWO).

He is (co-) author of two books on computational geometry, one of which has become the standard textbook in the area, and he published over 160 papers in peer-reviewed journals and conferences.

He was on the program committee of numerous international conferences on computational geometry, on algorithms, and on computer graphics, and he is on the editorial board of three international journals.

The research

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.

Four areas

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

Computational geometry
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.

I/O-efficient algorithms
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.

Graph drawing
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. 

Thesis projects

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.