## Abstract

We present an O(nlog ^{2}n+ (1 / ε) ^{5}nlog 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 / ε) ^{4}nlog ^{4}n+ 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 language | English (US) |
---|---|

Pages (from-to) | 3075-3098 |

Number of pages | 24 |

Journal | Algorithmica |

Volume | 81 |

Issue number | 8 |

DOIs | |

State | Published - 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