Faster Construction of a Planar Distance Oracle with Õ(1) Query Time

2025/03/24 by Boneh, Itai, Golan, Shay, Mozes, Shay +2
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2503.18425

Abstract

We show how to preprocess a weighted undirected n-vertex planar graph in O(n^4/3) time, such that the distance between any pair of vertices can then be reported in O(1) time. This improves the previous O(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 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'23].

Related

• Better Tradeoffs for Exact Distance Oracles in Planar Graphs
• Planar Distance Oracles with Better Time-Space Tradeoffs
• Constant Query Time (1 + ε)-Approximate Distance Oracle for Planar Graphs
• Fast and Compact Exact Distance Oracle for Planar Graphs
• Approximate Distance Oracles for Planar Graphs with Improved Query Time-Space Tradeoff