TY - GEN

T1 - All-pairs shortest paths in geometric intersection graphs

AU - Chan, Timothy M.

AU - Skrepetos, Dimitrios

N1 - Publisher Copyright:
© Springer International Publishing AG 2017.

PY - 2017

Y1 - 2017

N2 - We address the All-Pairs Shortest Paths (APSP) problem for a number of unweighted, undirected geometric intersection graphs. We present a general reduction of the problem to static, offline intersection searching (specifically detection). As a consequence, we can solve APSP for 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 boxes in O (n2 logd−1.5 n) time for d ≥ 2, and 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. In addition, we show how to solve the Single-Source Shortest Paths (SSSP) problem in unweighted intersection graphs of axis-aligned line segments in O (n log n) time, by a reduction to dynamic orthogonal point location.

AB - We address the All-Pairs Shortest Paths (APSP) problem for a number of unweighted, undirected geometric intersection graphs. We present a general reduction of the problem to static, offline intersection searching (specifically detection). As a consequence, we can solve APSP for 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 boxes in O (n2 logd−1.5 n) time for d ≥ 2, and 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. In addition, we show how to solve the Single-Source Shortest Paths (SSSP) problem in unweighted intersection graphs of axis-aligned line segments in O (n log n) time, by a reduction to dynamic orthogonal point location.

KW - Disk graphs

KW - Geometric intersection graphs

KW - Intersection searching data structures

KW - Shortest paths

UR - http://www.scopus.com/inward/record.url?scp=85025154774&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85025154774&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-62127-2_22

DO - 10.1007/978-3-319-62127-2_22

M3 - Conference contribution

AN - SCOPUS:85025154774

SN - 9783319621265

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 253

EP - 264

BT - Algorithms and Data Structures - 15th International Symposium, WADS 2017, Proceedings

A2 - Ellen, Faith

A2 - Kolokolova, Antonina

A2 - Sack, Jorg-Rudiger

PB - Springer

T2 - 15th International Symposium on Algorithms and Data Structures, WADS 2017

Y2 - 31 July 2017 through 2 August 2017

ER -