All-pairs shortest paths in geometric intersection graphs

Timothy M. Chan, Dimitrios Skrepetos

Research output: Chapter in Book/Report/Conference proceedingConference 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 (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.

Original languageEnglish (US)
Title of host publicationAlgorithms and Data Structures - 15th International Symposium, WADS 2017, Proceedings
EditorsFaith Ellen, Antonina Kolokolova, Jorg-Rudiger Sack
PublisherSpringer
Pages253-264
Number of pages12
ISBN (Print)9783319621265
DOIs
StatePublished - 2017
Event15th International Symposium on Algorithms and Data Structures, WADS 2017 - St. John’s, Canada
Duration: Jul 31 2017Aug 2 2017

Publication series

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

Other

Other15th International Symposium on Algorithms and Data Structures, WADS 2017
Country/TerritoryCanada
CitySt. John’s
Period7/31/178/2/17

Keywords

  • Disk graphs
  • Geometric intersection graphs
  • Intersection searching data structures
  • Shortest paths

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

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

Cite this