Abstract
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 2 [n; n2], we show an oracle of size S that answers queries in ~O (maxf1; n1:5=Sg) 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 2 [n; n5=3].
| Originalsprog | Engelsk |
|---|---|
| Titel | Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms |
| Redaktører | A. Czumaj |
| Forlag | Society for Industrial and Applied Mathematics |
| Publikationsdato | 2018 |
| Sider | 515-529 |
| ISBN (Elektronisk) | 9781611975031 |
| DOI | |
| Status | Udgivet - 2018 |
| Begivenhed | 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 - New Orleans, USA Varighed: 7 jan. 2018 → 10 jan. 2018 |
Konference
| Konference | 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 |
|---|---|
| Land/Område | USA |
| By | New Orleans |
| Periode | 07/01/2018 → 10/01/2018 |
| Sponsor | ACM Special Interest Group on Algorithms and Computation Theory (SIGACT), SIAM Activity Group on Discrete Mathematics |