This seminar is offered for students enrolled in the Mathematics Master as module S4C1 as well as students enrolled in the Computer Science Master as module MA-INF 1205. The full title of the module is Graduate Seminar Discrete Optimization – Abstract Voronoi Diagrams and Planar Distance Oracles. The seminar is organized and held by Prof. Dr. Anne Driemel.
The goal of the seminar is for each participant to:
The first meeting for the seminar will take on Friday October 15, 2021, at 2:15 pm. The room will be announced shortly in advance. If you are interested to participate in the seminar and want to receive updates, please contact Prof. Dr. Anne Driemel.
The assignment of topics and the schedule of talks will be decided in or shortly after the first meeting.
The topic of the seminar is centered around abstract Voronoi diagrams and how they can be used to obtain better distance oracles for planar graphs. A distance oracle is a data structure that stores a graph and that can answer queries for the shortest path distance between vertices. In general, for any data structure, we are interested in the preprocessing time, space and the query time that is achieved by the data structure. For distance oracles, this question is also related to fundamental graph questions, such as, how fast can we compute the diameter of a graph. Recent complexity theoretic result suggest that this problem cannot be solved in strongly subquadratic time in the number of vertices of the graph. In this seminar we will take a closer look at some recent results that make use of abstract Voronoi diagrams. This approach was first suggested by Cabello in 2017. Abstract Voronoi diagrams have been known much longer. They were introduced by Klein in 1987.