Seminar Details

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.