Loh, Po-Shen (2003) Finding Shortest Paths With Computational Geometry. Journal of Graph Algorithms and Applications, 7 (3). pp. 287-303. ISSN 1526-1719. https://resolver.caltech.edu/CaltechAUTHORS:LOHjgaa03
![]()
|
PDF
See Usage Policy. 231kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:LOHjgaa03
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.
Item Type: | Article | ||||||
---|---|---|---|---|---|---|---|
Related URLs: |
| ||||||
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. | ||||||
Issue or Number: | 3 | ||||||
Record Number: | CaltechAUTHORS:LOHjgaa03 | ||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:LOHjgaa03 | ||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||
ID Code: | 756 | ||||||
Collection: | CaltechAUTHORS | ||||||
Deposited By: | Archive Administrator | ||||||
Deposited On: | 27 Sep 2005 | ||||||
Last Modified: | 02 Oct 2019 22:36 |
Repository Staff Only: item control page