2026-08-10T17:31:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7838 2024-03-06T10:41:18Z ddc:004 open_access

Faster Approximate Diameter and Distance Oracles in Planar Graphs Chan, Timothy M. Skrepetos, Dimitrios planar graphs diameter abstract Voronoi diagrams We present an algorithm that computes a (1+varepsilon)-approximation of the diameter of a weighted, undirected planar graph of n vertices with non-negative edge lengths in O(nlog n(log n + (1/varepsilon)^5)) expected time, improving upon the O(n((1/varepsilon)^4 log^4(n) + 2^{O(1/varepsilon)}))-time algorithm of Weimann and Yuster [ICALP 2013]. Our algorithm makes two improvements over that result: first and foremost, it replaces the exponential dependency on 1/varepsilon with a polynomial one, by adapting and specializing Cabello's recent abstract-Voronoi-diagram-based technique [SODA 2017] for approximation purposes; second, it shaves off two logarithmic factors by choosing a better sequence of error parameters during recursion. Moreover, using similar techniques, we improve the (1+varepsilon)-approximate distance oracle of Gu and Xu [ISAAC 2015] by first replacing the exponential dependency on 1/varepsilon on the preprocessing time and space with a polynomial one and second removing a logarithmic factor from the preprocessing time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Timothy M. Chan and Dimitrios Skrepetos 2017 Is Part Of LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2017.25 urn:nbn:de:0030-drops-78382 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.25 eng https://creativecommons.org/licenses/by/3.0/legalcode