DIKU Bits: Irrational guards are sometimes needed

Speaker

Mikkel Abrahamsen, Assistant professor, Algorithms and Complexity Section, DIKU.

Abstract

In this talk I will explain why it is sometimes optimal for an art gallery guard to be irrational. In the Art Gallery Problem, we are given a map of an art gallery with straight walls (a simple polygon) as input, and we have to place some guards (points) in the gallery, each of which sees all points to which the line of sight is not blocked by a wall. The question is how many guards are needed in order to watch over the entire gallery. You will see that even when all the corners of the gallery have integer coordinates, it is sometimes necessary for the guards to stand at points with irrational coordinates if we want to use the minimum number of guards. I will also explain why some people (=me!) care about investigating such a question by outlining the implications of the result for the computational complexity of the Art Gallery Problem.

Zooming in on Mikkel Abrahamsen

Which courses do you teach? (BSc and MSc)
I teach Advanced Algorithms and Data Structures (AADS, MSc) and Approximation Algorithms (APX, MSc).

Which technology/research/projects/startup are you excited to see the evolution of?
I’m excited about the development of self-driving cars. On the theoretical side, I like all kinds of discrete and computational geometry, and also algorithms and data structures in general.

What is your favorite sketch from the DIKUrevy?
I have to catch up on my DIKUrevyen knowledge. Looking forward to watching the next one!