Almost Optimal Exact Distance Oracles for Planar Graphs ∗

We consider the problem of preprocessing a weighted directed planar graph in order to quickly answer exact distance queries. The main tension in this problem is between space S and query time Q , and since the mid-1990s all results had polynomial time-space tradeo ﬀ s, e.g., Q = ˜ Θ ( n/ √ S ) or Q = ˜ Θ ( n 5 / 2 /S 3 / 2 ). In this paper we show that there is no polynomial tradeo ﬀ between time and space and that it is possible to simultaneously achieve almost optimal space n 1+ o (1) and almost optimal query time n o (1) . More precisely, we achieve the following space-time tradeo ﬀ s: n and 2+ o and n time, n / and We reduce a distance query to a variety of point location problems in additively weighted Voronoi diagrams , and develop new algorithms for the point location problem itself using several partially persistent dynamic tree data structures.