Better tradeoffs for exact distance oracles in planar graphs
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Standard
Better tradeoffs for exact distance oracles in planar graphs. / Gawrychowski, Pawel; Mozes, Shay; Weimann, Oren; Wulff-Nilsen, Christian.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms . red. / A. Czumaj. Society for Industrial and Applied Mathematics, 2018. s. 515-529.Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Better tradeoffs for exact distance oracles in planar graphs
AU - Gawrychowski, Pawel
AU - Mozes, Shay
AU - Weimann, Oren
AU - Wulff-Nilsen, Christian
PY - 2018
Y1 - 2018
N2 - 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].
AB - 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].
UR - http://www.scopus.com/inward/record.url?scp=85045541984&partnerID=8YFLogxK
U2 - 10.1137/1.9781611975031.34
DO - 10.1137/1.9781611975031.34
M3 - Article in proceedings
AN - SCOPUS:85045541984
SP - 515
EP - 529
BT - Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms
A2 - Czumaj, A.
PB - Society for Industrial and Applied Mathematics
T2 - 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
Y2 - 7 January 2018 through 10 January 2018
ER -
ID: 204040383