@inproceedings{9042b7b41a6a4bff942dea64bad3304c,
title = "Faster Construction of a Planar Distance Oracle with {\~O}(1) Query Time",
abstract = "We show how to preprocess a weighted undirected n-vertex planar graph in {\~O}(n4/3) time, such that the distance between any pair of vertices can then be reported in {\~O}(1) time. This improves the previous {\~O}(n3/2) preprocessing time [JACM{\textquoteright}23]. Our main technical contribution is a near optimal construction of additively weighted Voronoi diagrams in undirected planar graphs. Namely, given a planar graph G and a face f, we show that one can preprocess G in {\~O}(n) time such that given any weight assignment to the vertices of f one can construct the additively weighted Voronoi diagram of f in near optimal {\~O}(|f|) time. This improves the {\~O}(√n|f|) construction time of [JACM{\textquoteright}23].",
keywords = "Construction Time, Distance Oracle, Planar Graph",
author = "Itai Boneh and Shay Golan and Shay Mozes and Daniel Prigan and Oren Weimann",
note = "Publisher Copyright: {\textcopyright} Itai Boneh, Shay Golan, Shay Mozes, Daniel Prigan, and Oren Weimann.; 52nd EATCS International Colloquium on Automata, Languages, and Programming, ICALP 2025 ; Conference date: 08-07-2025 Through 11-07-2025",
year = "2025",
month = jun,
day = "30",
doi = "10.4230/LIPIcs.ICALP.2025.33",
language = "אנגלית",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Keren Censor-Hillel and Fabrizio Grandoni and Joel Ouaknine and Gabriele Puppis",
booktitle = "52nd International Colloquium on Automata, Languages, and Programming, ICALP 2025",
address = "גרמניה",
}