Almost Optimal Exact Distance Oracles for Planar Graphs
| Autor: | Panagiotis Charalampopoulos, Paweł Gawrychowski, Yaowei Long, Shay Mozes, Seth Pettie, Oren Weimann, Christian Wulff-Nilsen |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Zdroj: | Journal of the ACM. 70:1-50 |
| ISSN: | 1557-735X 0004-5411 |
| DOI: | 10.1145/3580474 |
| Popis: | 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 tradeoffs, e.g., Q = ~ Θ( n/√ S ) or Q = ~Θ( n 5/2 /S 3/2 ). In this article we show that there is no polynomial tradeoff 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 tradeoffs: n 1+ o (1) space and log 2+ o (1) n query time, n log 2+ o (1) n space and n o (1) query time, n 4/3+ o (1) space and log 1+ o (1) n query time. 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|