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

Charalampopoulos, P, Gawrychowski, P, Long, Y, Mozes, S, Pettie, S, Weimann, O & Wulff-Nilsen, C 2023, 'Almost Optimal Exact Distance Oracles for Planar Graphs', Journal of the ACM, vol. 70, no. 2, 12. https://doi.org/10.1145/3580474

APA

Charalampopoulos, P., Gawrychowski, P., Long, Y., Mozes, S., Pettie, S., Weimann, O., & Wulff-Nilsen, C. (2023). Almost Optimal Exact Distance Oracles for Planar Graphs. Journal of the ACM, 70(2), [12]. https://doi.org/10.1145/3580474

Vancouver

Charalampopoulos P, Gawrychowski P, Long Y, Mozes S, Pettie S, Weimann O et al. Almost Optimal Exact Distance Oracles for Planar Graphs. Journal of the ACM. 2023;70(2). 12. https://doi.org/10.1145/3580474

Author

Charalampopoulos, Panagiotis ; Gawrychowski, Paweł ; Long, Yaowei ; Mozes, Shay ; Pettie, Seth ; Weimann, Oren ; Wulff-Nilsen, Christian. / Almost Optimal Exact Distance Oracles for Planar Graphs. In: Journal of the ACM. 2023 ; Vol. 70, No. 2.

Bibtex

@article{8982e0fccb6a435e9328bb42fe5c9a0c,

title = "Almost Optimal Exact Distance Oracles for Planar Graphs",

abstract = "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. ",

keywords = "distance oracles, persistent data structures, Planar graphs, Voronoi diagrams",

author = "Panagiotis Charalampopoulos and Pawe{\l} Gawrychowski and Yaowei Long and Shay Mozes and Seth Pettie and Oren Weimann and Christian Wulff-Nilsen",

note = "Publisher Copyright: {\textcopyright} 2023 Copyright held by the owner/author(s). Publication rights licensed to ACM.",

year = "2023",

doi = "10.1145/3580474",

language = "English",

volume = "70",

journal = "Journal of the ACM",

issn = "0004-5411",

publisher = "Association for Computing Machinery",

number = "2",

}

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

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

Department of Computer Science