Karczmarz, Adam ;
Pawlewicz, Jakub ;
Sankowski, Piotr
Sublinear AverageCase Shortest Paths in Weighted UnitDisk Graphs
Abstract
We consider the problem of computing shortest paths in weighted unitdisk graphs in constant dimension d. Although the singlesource and allpairs variants of this problem are wellstudied in the plane case, no nontrivial exact distance oracles for unitdisk graphs have been known to date, even for d = 2.
The classical result of Sedgewick and Vitter [Algorithmica '86] shows that for weighted unitdisk graphs in the plane the A^* search has averagecase performance superior to that of a standard shortest path algorithm, e.g., Dijkstra’s algorithm. Specifically, if the n corresponding points of a weighted unitdisk graph G are picked from a unit square uniformly at random, and the connectivity radius is r ∈ (0,1), A^* finds a shortest path in G in O(n) expected time when r = Ω(√{log n/n}), even though G has Θ((nr)²) edges in expectation. In other words, the work done by the algorithm is in expectation proportional to the number of vertices and not the number of edges.
In this paper, we break this natural barrier and show even stronger sublinear time results. We propose a new heuristic approach to computing pointtopoint exact shortest paths in unitdisk graphs. We analyze the averagecase behavior of our heuristic using the same random graph model as used by Sedgewick and Vitter and prove it superior to A^*. Specifically, we show that, if we are able to report the set of all k points of G from an arbitrary rectangular region of the plane in O(k + t(n)) time, then a shortest path between arbitrary two points of such a random graph on the plane can be found in O(1/r² + t(n)) expected time. In particular, the stateoftheart range reporting data structures imply a sublinear expected bound for all r = Ω(√{log n/n}) and O(√n) expected bound for r = Ω(n^{1/4}) after only nearlinear preprocessing of the point set.
Our approach naturally generalizes to higher dimensions d ≥ 3 and yields sublinear expected bounds for all d = O(1) and sufficiently large r.
BibTeX  Entry
@InProceedings{karczmarz_et_al:LIPIcs.SoCG.2021.46,
author = {Karczmarz, Adam and Pawlewicz, Jakub and Sankowski, Piotr},
title = {{Sublinear AverageCase Shortest Paths in Weighted UnitDisk Graphs}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {46:146:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771849},
ISSN = {18688969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13845},
URN = {urn:nbn:de:0030drops138454},
doi = {10.4230/LIPIcs.SoCG.2021.46},
annote = {Keywords: unitdisk graphs, shortest paths, distance oracles}
}
02.06.2021
Keywords: 

unitdisk graphs, shortest paths, distance oracles 
Seminar: 

37th International Symposium on Computational Geometry (SoCG 2021)

Issue date: 

2021 
Date of publication: 

02.06.2021 