2026-07-26T20:11:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23410 2025-10-02T12:54:23Z ddc:004 open_access

Faster Construction of a Planar Distance Oracle with Õ(1) Query Time Boneh, Itai Golan, Shay Mozes, Shay Prigan, Daniel Weimann, Oren Distance Oracle Planar Graph Construction Time We show how to preprocess a weighted undirected n-vertex planar graph in Õ(n^{4/3}) time, such that the distance between any pair of vertices can then be reported in Õ(1) time. This improves the previous Õ(n^{3/2}) preprocessing time [JACM'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 Õ(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 Õ(|f|) time. This improves the Õ(√{n|f|}) construction time of [JACM'23]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Itai Boneh and Shay Golan and Shay Mozes and Daniel Prigan and Oren Weimann 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.33 urn:nbn:de:0030-drops-234106 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.33 eng https://creativecommons.org/licenses/by/4.0/legalcode