Two algorithms for a reachability problem in one-dimensional space |
| |
Authors: | Dajin Wang Sutner K |
| |
Affiliation: | Dept. of Comput. Sci., Montclair State Univ., Upper Montclair, NJ; |
| |
Abstract: | Two algorithms are proposed to solve a reachability problem among time-dependent obstacles in 1D 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 |
| |
Keywords: | |
|
|