Calculating points, lines, and rectangles, how hard can it be?

PhD defence, Tuesday 12 September 2017. Ingo van Duijn.

2017.09.12 | Steffi Hjerrild Iversen

Ingo van Duijn

During his studies, Ingo van Duijn researched fundamental algorithmic problems in computer science. Characteristic of a fundamental problem is that it can be understood in its entirety using a basic framework. For instance, within the geometric framework of points and lines in the plane, one can easily ask and understand the question: "Given a drawing of n points and the instruction to cover them with the minimum number of straight lines, how do you figure out which lines to draw?". Ingo van Duijn studied this and other algorithmic problems, relating their inherent difficulty to deep results in their respective frameworks.

Among others, the research findings show that for the problem with points and lines, there exist theoretically faster methods of deciding which lines to draw than previously known. Other results include showing that in settings where shuffling vast amounts of data is hard (viz. permuting in the I/O model), this “hardness” is inherited by various seemingly unrelated geometric problems.

The PhD degree was completed at the Department of Computer Science, Science and Technology, Aarhus University.

This résumé was prepared by the PhD student.

Time: Tuesday 12 September 2017 at 13.00
Place: Building 5342, room 333, ADA, Department of Computer Science, Aarhus University, Åbogade 34, 8200 Aarhus N
Title of dissertation: Algorithmic Aspects of Arrangements and Incidences
Contact information: Ingo van Duijn, e-mail: ivd@cs.au.dk  
Members of the assessment committee:
Chancellor's Professor Michael T. Goodrich, Department of Computer Science, University of California, Irvine
Associate Professor Riko Jacob, Theoretical Computer Science Section of IT University of Copenhagen
Associate Professor Ira Assent, Department of Computer Science, Aarhus University (chair)
Main supervisor:
Associate Professor Peyman Afshani, Department of Computer Science, Aarhus University
Language: The PhD dissertation will be defended in English

The defence is public.
The dissertation is available for reading at the Graduate School of Science and Technology/GSST, Ny Munkegade 120, building 1520, rooms 128-134, 8000 Aarhus C.

PhD defence
Comments on content: 
Revised 20.09.2017