Faster Approximate Diameter and Distance Oracles in Planar Graphs

Timothy M. Chan, Dimitrios Skrepetos

Research output: Contribution to journalArticlepeer-review

Abstract

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

Original languageEnglish (US)
Pages (from-to)3075-3098
Number of pages24
JournalAlgorithmica
Volume81
Issue number8
DOIs
StatePublished - Aug 1 2019

Keywords

  • Approximation algorithms
  • Diameter
  • Distance oracles
  • Planar graphs
  • Shortest paths
  • Voronoi diagrams

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Faster Approximate Diameter and Distance Oracles in Planar Graphs'. Together they form a unique fingerprint.

Cite this