All-pairs shortest paths in geometric intersection graphs

Timothy M. Chan, Dimitrios Skrepetos

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)27-41
Number of pages15
JournalJournal of Computational Geometry
Volume10
Issue number1
StatePublished - 2019

ASJC Scopus subject areas

  • Geometry and Topology
  • Computer Science Applications
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'All-pairs shortest paths in geometric intersection graphs'. Together they form a unique fingerprint.

Cite this