Seminar: Abstract Voronoi Diagrams and Planar Distance Oracles

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:

  • Study a scientific paper (see references below)
  • Present the main ideas of the paper in a talk (45 Minutes)
  • Participate in discussions on the topic of the seminar
  • Submit a written report (in own words) (10 pages)

Schedule

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.

Content

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.

Literature (tentative)

  1. Klein, Rolf, Kurt Mehlhorn, Stefan Meiser. “Randomized incremental construction of abstract Voronoi diagrams”. Computational Geometry 3(1993), 157-184.
  2. Cabello, Sergio. “Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs.” ACM Transactions on Algorithms (TALG) 15.2 (2018): 1-38.
  3. Gawrychowski, Pawel, et al. “Better tradeoffs for exact distance oracles in planar graphs.” Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2018.
  4. Cohen-Addad, Vincent, Søren Dahlgaard, and Christian Wulff-Nilsen. “Fast and compact exact distance oracle for planar graphs.” 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2017.
  5. Gawrychowski, Paweł, et al. “Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic O(n^5/3) Time.” SIAM Journal on Computing 50.2 (2021): 509-554.
  6. Charalampopoulos, Panagiotis, et al. “Almost optimal distance oracles for planar graphs.” Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. 2019.
  7. Long, Yaowei, and Seth Pettie. “Planar Distance Oracles with Better Time-Space Tradeoffs.” Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, 2021.
  8. Chan, Timothy M., and Dimitrios Skrepetos. “Faster approximate diameter and distance oracles in planar graphs.” Algorithmica 81.8 (2019): 3075-3098.

Page Tools