Faster Approximate Diameter and Distance Oracles in Planar Graphs

摘要

We present an O (1/epsilon)5 -time algorithm that computes a (1+epsilon)-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 time in two regards. First we eliminate the exponential dependency on 1/epsilon 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+epsilon)-approximate distance oracle (Gu and Xu, in: Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC), 2015) with polynomial dependency on 1/epsilon in the preprocessing time and space and O query time.