Organizer(s):

Sepehr Assadi, Rutgers University

Swastik Kopparty, Rutgers University

Seth Pettie, University of Michigan

Abstract

We consider the problem of preprocessing a weighted planar graph in order to answer exact distance and shortest path queries. As in the recent algorithms of Cohen-Addad et al. (2017), Gawrychowski et al. (2018), and Charalampopoulos et al. (2019), our algorithm is based on solving the point-location problem in weighted planar Voronoi diagrams. We give a new, efficient method to solve point location using persistent data structures, which leads to a new time-space tradeoff for the problem. At the extremes of this tradeoff, the data structure: * occupies $n^{1+o(1)}$ space and answers distance queries in $log^{2+o(1)} n$ time, or * occupies $nlog^{2+o(1)} n$ space and answers distance queries in $n^{o(1)}$ time. Joint work with Yaowei Long, to appear in SODA 2021.

The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar.

See: https://sites.google.com/view/dimacs-theory-seminar/home

Please contact the organizers:

Sepehr Assadi and Swastik Kopparty  for the link