2026-07-25T13:34:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8737 2024-03-06T10:42:32Z ddc:004 open_access

Approximate Shortest Paths and Distance Oracles in Weighted Unit-Disk Graphs Chan, Timothy M. Skrepetos, Dimitrios shortest paths distance oracles unit-disk graphs planar graphs We present the first near-linear-time (1 + epsilon)-approximation algorithm for the diameter of a weighted unit-disk graph of n vertices, running in O(n log^2 n) time, for any constant epsilon>0, improving the near-O(n^{3/2})-time algorithm of Gao and Zhang [STOC 2003]. Using similar ideas, we can construct a (1+epsilon)-approximate distance oracle for weighted unit-disk graphs with O(1) query time, with a similar improvement in the preprocessing time, from near O(n^{3/2}) to O(n log^3 n). We also obtain new results for a number of other related problems in the weighted unit-disk graph metric, such as the radius and bichromatic closest pair. As a further application, we use our new distance oracle, along with additional ideas, to solve the (1 + epsilon)-approximate all-pairs bounded-leg shortest paths problem for a set of n planar points, with near O(n^{2.579}) preprocessing time, O(n^2 log n) space, and O(log{log n}) query time, improving thus the near-cubic preprocessing bound by Roditty and Segal [SODA 2007]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Timothy M. Chan and Dimitrios Skrepetos 2018 Is Part Of LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2018.24 urn:nbn:de:0030-drops-87375 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.24 eng https://creativecommons.org/licenses/by/3.0/legalcode