Better Tradeoffs for Exact Distance Oracles in Planar Graphs
Paweł Gawrychowski, Shay Mozes, Oren Weimann, Christian Wulff‐Nilsen · Society for Industrial and Applied Mathematics eBooks · 2018
We present an O(n1.5)-space distance oracle for directed planar graphs that answers distance queries in O(log n) time. Our oracle both significantly simplifies and significantly improves the recent oracle of Cohen-Addad, Dahlgaard and Wulff-Nilsen [FOCS 2017], which uses O(n5/3)-space and answers queries in O(log n) time. We achieve this by designing an elegant and efficient point location data structure for Voronoi diagrams on planar graphs. We further show a smooth tradeoff between space and query-time. For any S ∊ [n, n2], we show an oracle of size S that answers queries in Õ(max{1, n1.5/S}) time. This new tradeoff is currently the best (up to polylogarithmic factors) for the entire range of S and improves by polynomial factors over all previously known tradeoffs for the range S ∊ [n, n5/3].