All-pairs shortest paths in geometric intersection graphs

Timothy M. Chan; Dimitrios Skrepetos

doi:10.1007/978-3-319-62127-2_22

All-pairs shortest paths in geometric intersection graphs

Timothy M. Chan, Dimitrios Skrepetos

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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 (n² log n) time, axis-aligned line segments in O (n² log log n) time, arbitrary line segments in O (n^7/3 log^1/3 n) time, d-dimensional axis-aligned boxes in O (n² log^d−1.5 n) time for d ≥ 2, and d-dimensional axis-aligned unit hypercubes in O (n² log log n) time for d = 3 and O (n² log^d−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.

Original language	English (US)
Title of host publication	Algorithms and Data Structures - 15th International Symposium, WADS 2017, Proceedings
Editors	Faith Ellen, Antonina Kolokolova, Jorg-Rudiger Sack
Publisher	Springer
Pages	253-264
Number of pages	12
ISBN (Print)	9783319621265
DOIs	https://doi.org/10.1007/978-3-319-62127-2_22
State	Published - 2017
Event	15th International Symposium on Algorithms and Data Structures, WADS 2017 - St. John’s, Canada Duration: Jul 31 2017 → Aug 2 2017

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10389 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	15th International Symposium on Algorithms and Data Structures, WADS 2017
Country/Territory	Canada
City	St. John’s
Period	7/31/17 → 8/2/17

Keywords

Disk graphs
Geometric intersection graphs
Intersection searching data structures
Shortest paths

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Online availability

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

Library availability

Discover UIUC Full Text

Cite this

Chan, T. M., & Skrepetos, D. (2017). All-pairs shortest paths in geometric intersection graphs. In F. Ellen, A. Kolokolova, & J-R. Sack (Eds.), Algorithms and Data Structures - 15th International Symposium, WADS 2017, Proceedings (pp. 253-264). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10389 LNCS). Springer. https://doi.org/10.1007/978-3-319-62127-2_22

All-pairs shortest paths in geometric intersection graphs. / Chan, Timothy M.; Skrepetos, Dimitrios.

Algorithms and Data Structures - 15th International Symposium, WADS 2017, Proceedings. ed. / Faith Ellen; Antonina Kolokolova; Jorg-Rudiger Sack. Springer, 2017. p. 253-264 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10389 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Chan, TM & Skrepetos, D 2017, All-pairs shortest paths in geometric intersection graphs. in F Ellen, A Kolokolova & J-R Sack (eds), Algorithms and Data Structures - 15th International Symposium, WADS 2017, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10389 LNCS, Springer, pp. 253-264, 15th International Symposium on Algorithms and Data Structures, WADS 2017, St. John’s, Canada, 7/31/17. https://doi.org/10.1007/978-3-319-62127-2_22

Chan TM, Skrepetos D. All-pairs shortest paths in geometric intersection graphs. In Ellen F, Kolokolova A, Sack J-R, editors, Algorithms and Data Structures - 15th International Symposium, WADS 2017, Proceedings. Springer. 2017. p. 253-264. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-62127-2_22

Chan, Timothy M. ; Skrepetos, Dimitrios. / All-pairs shortest paths in geometric intersection graphs. Algorithms and Data Structures - 15th International Symposium, WADS 2017, Proceedings. editor / Faith Ellen ; Antonina Kolokolova ; Jorg-Rudiger Sack. Springer, 2017. pp. 253-264 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{cab43d6ae3864363a73170bb03412f1a,

title = "All-pairs shortest paths in geometric intersection graphs",

abstract = "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.",

keywords = "Disk graphs, Geometric intersection graphs, Intersection searching data structures, Shortest paths",

author = "Chan, {Timothy M.} and Dimitrios Skrepetos",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2017.; 15th International Symposium on Algorithms and Data Structures, WADS 2017 ; Conference date: 31-07-2017 Through 02-08-2017",

year = "2017",

doi = "10.1007/978-3-319-62127-2_22",

language = "English (US)",

isbn = "9783319621265",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "253--264",

editor = "Faith Ellen and Antonina Kolokolova and Jorg-Rudiger Sack",

booktitle = "Algorithms and Data Structures - 15th International Symposium, WADS 2017, Proceedings",

address = "Germany",

}

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 -

All-pairs shortest paths in geometric intersection graphs

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this