Almost Optimal Exact Distance Oracles for Planar Graphs
Research output: Contribution to journal › Journal article › Research › peer-review
Standard
Almost Optimal Exact Distance Oracles for Planar Graphs. / Charalampopoulos, Panagiotis; Gawrychowski, Paweł; Long, Yaowei; Mozes, Shay; Pettie, Seth; Weimann, Oren; Wulff-Nilsen, Christian.
In: Journal of the ACM, Vol. 70, No. 2, 12, 2023.Research output: Contribution to journal › Journal article › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - Almost Optimal Exact Distance Oracles for Planar Graphs
AU - Charalampopoulos, Panagiotis
AU - Gawrychowski, Paweł
AU - Long, Yaowei
AU - Mozes, Shay
AU - Pettie, Seth
AU - Weimann, Oren
AU - Wulff-Nilsen, Christian
N1 - Publisher Copyright: © 2023 Copyright held by the owner/author(s). Publication rights licensed to ACM.
PY - 2023
Y1 - 2023
N2 - 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/g√S) or Q = ∼θ(n5/2/S3/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 n1+o(1) and almost optimal query time no(1). More precisely, we achieve the following space-time tradeoffs:n1+o(1) space and log2+o(1) n query time,n log2+o(1) n space and no(1) query time,n4/3+o(1) space and log1+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.
AB - 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/g√S) or Q = ∼θ(n5/2/S3/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 n1+o(1) and almost optimal query time no(1). More precisely, we achieve the following space-time tradeoffs:n1+o(1) space and log2+o(1) n query time,n log2+o(1) n space and no(1) query time,n4/3+o(1) space and log1+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.
KW - distance oracles
KW - persistent data structures
KW - Planar graphs
KW - Voronoi diagrams
UR - http://www.scopus.com/inward/record.url?scp=85158129842&partnerID=8YFLogxK
U2 - 10.1145/3580474
DO - 10.1145/3580474
M3 - Journal article
AN - SCOPUS:85158129842
VL - 70
JO - Journal of the ACM
JF - Journal of the ACM
SN - 0004-5411
IS - 2
M1 - 12
ER -
ID: 347309378