Two algorithms for a reachability problem in one-dimensional space

Dajin Wang, Klaus Sutner

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


Two algorithms are proposed to solve a reachability problem among time-dependent obstacles in one-dimensional (1-D) space. In the first approach, the motion planning problem is reduced to a path existence problem in a directed graph. The algorithm is very simple, with running time O(n2), where n is the complexity of obstacles in space-time. The second algorithm uses a sweep-line technique and has running time O(n log2 n). Besides, the latter algorithm can be easily modified to compute a collision-free trajectory, if such trajectories exist.

Original languageEnglish
Pages (from-to)478-486
Number of pages9
JournalIEEE Transactions on Systems, Man, and Cybernetics Part A:Systems and Humans.
Issue number4
StatePublished - 1998


  • Algorithmic robotics
  • Motion planning
  • Obstacles
  • Path planning
  • Reachability
  • Space-time
  • Sweep-line algorithm


Dive into the research topics of 'Two algorithms for a reachability problem in one-dimensional space'. Together they form a unique fingerprint.

Cite this