Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00071
Finding Shortest Paths With Computational Geometry
Po-Shen Loh
Vol. 7, no. 3, pp. 287-303, 2003. Regular paper.
Abstract We present a heuristic search algorithm for the Rd Manhattan shortest path
problem that achieves front-to-front bidirectionality in subquadratic time. In the
study of bidirectional search algorithms, front-to-front heuristic computations were
thought to be prohibitively expensive (at least quadratic time complexity); our
algorithm runs in O(n logd n) time and O(n logd−1 n) space, where n is the
number of visited vertices. We achieve this result by embedding the problem in
Rd+1 and identifying heuristic calculations as instances of a dynamic
closest-point problem, to which we then apply methods from computational geometry.
|
Journal Supporters
|