2026-08-19T00:08:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10464 2024-03-06T10:46:03Z ddc:004 open_access

Near-Optimal Algorithms for Shortest Paths in Weighted Unit-Disk Graphs Wang, Haitao Xue, Jie Single-source shortest paths Weighted unit-disk graphs Geometric graph algorithms We revisit a classical graph-theoretic problem, the single-source shortest-path (SSSP) problem, in weighted unit-disk graphs. We first propose an exact (and deterministic) algorithm which solves the problem in O(n log^2 n) time using linear space, where n is the number of the vertices of the graph. This significantly improves the previous deterministic algorithm by Cabello and Jejčič [CGTA'15] which uses O(n^{1+delta}) time and O(n^{1+delta}) space (for any small constant delta>0) and the previous randomized algorithm by Kaplan et al. [SODA'17] which uses O(n log^{12+o(1)} n) expected time and O(n log^3 n) space. More specifically, we show that if the 2D offline insertion-only (additively-)weighted nearest-neighbor problem with k operations (i.e., insertions and queries) can be solved in f(k) time, then the SSSP problem in weighted unit-disk graphs can be solved in O(n log n+f(n)) time. Using the same framework with some new ideas, we also obtain a (1+epsilon)-approximate algorithm for the problem, using O(n log n + n log^2(1/epsilon)) time and linear space. This improves the previous (1+epsilon)-approximate algorithm by Chan and Skrepetos [SoCG'18] which uses O((1/epsilon)^2 n log n) time and O((1/epsilon)^2 n) space. Because of the Omega(n log n)-time lower bound of the problem (even when approximation is allowed), both of our algorithms are almost optimal. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Haitao Wang and Jie Xue 2019 Is Part Of LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2019.60 urn:nbn:de:0030-drops-104649 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.60 eng https://creativecommons.org/licenses/by/3.0/legalcode