TY - JOUR
T1 - All-pairs shortest paths in geometric intersection graphs
AU - Chan, Timothy M.
AU - Skrepetos, Dimitrios
N1 - Publisher Copyright:
© 2019, Macodrum library, Carleton University. All rights reserved.
Copyright:
Copyright 2019 Elsevier B.V., All rights reserved.
PY - 2019
Y1 - 2019
N2 - We present a simple and general algorithm for the all-pairs shortest paths (APSP) problem in unweighted geometric intersection graphs. Specifically we reduce the problem to the design of static data structures for offline intersection detection. Consequently we can solve APSP in unweighted intersection graphs of n arbitrary disks in O(n2 log n) time, axis-aligned line segments in O(n2 log log n) time, arbitrary line segments in O (n7/3 log1/3 n) time, d-dimensional axis-aligned unit hypercubes in O(n2 log log n) time for d = 3 and O(n2 logd−3 n) time for d ≥ 4, and d-dimensional axis-aligned boxes in O(n2 logd−1.5 n) time for d ≥ 2. We also reduce the single-source shortest paths (SSSP) problem in unweighted geometric intersection graphs to decremental intersection detection. Thus, we obtain an O (n log n)-time SSSP algorithm in unweighted intersection graphs of n axis-aligned line segments.
AB - We present a simple and general algorithm for the all-pairs shortest paths (APSP) problem in unweighted geometric intersection graphs. Specifically we reduce the problem to the design of static data structures for offline intersection detection. Consequently we can solve APSP in unweighted intersection graphs of n arbitrary disks in O(n2 log n) time, axis-aligned line segments in O(n2 log log n) time, arbitrary line segments in O (n7/3 log1/3 n) time, d-dimensional axis-aligned unit hypercubes in O(n2 log log n) time for d = 3 and O(n2 logd−3 n) time for d ≥ 4, and d-dimensional axis-aligned boxes in O(n2 logd−1.5 n) time for d ≥ 2. We also reduce the single-source shortest paths (SSSP) problem in unweighted geometric intersection graphs to decremental intersection detection. Thus, we obtain an O (n log n)-time SSSP algorithm in unweighted intersection graphs of n axis-aligned line segments.
UR - http://www.scopus.com/inward/record.url?scp=85066627447&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85066627447&partnerID=8YFLogxK
M3 - Article
AN - SCOPUS:85066627447
VL - 10
SP - 27
EP - 41
JO - Journal of Computational Geometry
JF - Journal of Computational Geometry
SN - 1920-180X
IS - 1
ER -