Published 2003
| public
Journal Article
Open
Finding Shortest Paths With Computational Geometry
- Creators
- Loh, Po-Shen
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.
Additional Information
Communicated by Joseph S.B. Mitchell: submitted October 2002; revised June 2003. Research supported by Axline and Larson fellowships from the California Institute of Technology. Special thanks to Alain Martin and Mika Nystr¨om for introducing this problem to the author, and to Charles Leiserson for providing pointers toward related literature. Thanks also to Po-Ru Loh for providing many valuable suggestions that significantly improved the clarity of this paper.Files
LOHjgaa03.pdf
Files
(231.3 kB)
Name | Size | Download all |
---|---|---|
md5:c3c1205732480bf619fda906cf2ae0c0
|
231.3 kB | Preview Download |
Additional details
- Eprint ID
- 756
- Resolver ID
- CaltechAUTHORS:LOHjgaa03.908
- Created
-
2005-09-27Created from EPrint's datestamp field
- Updated
-
2022-10-05Created from EPrint's last_modified field