Faster Approximate Diameter and Distance Oracles in Planar Graphs

We present an \(O\left( n\log ^2{n} +(1/\varepsilon )^5 n\log {n}\right) \)-time algorithm that computes a \((1+\varepsilon )\)-approximation of the diameter of a non-negatively-weighted, undirected planar graph of n vertices. This is an improvement over the algorithm of Weimann and Yuster (ACM Trans Algorithms 12(1):12, 2016) of \(O\left( (1/\varepsilon )^4 n\log ^4{n}+2^{O(1/\varepsilon )}n\right) \) time in two regards. First we eliminate the exponential dependency on \(1/\varepsilon \) by adapting and specializing Cabello’s recent Voronoi-diagram-based technique (Cabello, in: Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2017) for approximation purposes. Second we shave off two logarithmic factors by choosing a better sequence of error parameters in the recursion. Moreover, using similar techniques we obtain a variant of Gu and Xu’s \((1+\varepsilon )\)-approximate distance oracle (Gu and Xu, in: Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC), 2015) with polynomial dependency on \(1/\varepsilon \) in the preprocessing time and space and \(O\left( \log (1/\varepsilon )\right) \) query time.