We consider the problem of determining shortest paths in the presence of polyhe dral obstacles between two points in Euclidean three-space. For the special case when paths are constrained to the surfaces of three-dimensional objects, simple planar unfoldings are used to obtain the shortest path. For the general case when paths are not constrained to lie on any surface, we describe general ized unfoldings wherein the shortest path in three-space again becomes a straight line. These unfoldings of consist of multiple rotations about the edges of the polyhedral obstacles.
Get full access to this article
View all access options for this article.
References
1.
Bajaj, C.1985 (Urbana, Illinois). The algebraic complexity of shortest paths in polyhedral spaces. Proc. 23rd Ann. Allerton Conf. on Communication, Control and Computing, pp. 510-517.
2.
Bajaj, C.1986a (Waterloo, Canada). Limitations to algorithmic solvability: Galois methods and models of computation. Proc. ACM Symp. on Symbolic and Algebraic Computation, pp. 71-76.
3.
Bajaj, C.1986b. An efficient parallel solution for Euclidean shortest paths in three dimensions. Proc. IEEE Conf. on Robotics and Automation, pp. 1897-1900.
4.
Franklin, R., Akman, V., and Verrili, C.1985. Voronoi diagrams with barriers and on polyhedra for minimal path planning. The VisualComputer1:133-150.
5.
Lozano-Pérez, T., and Wesley, M.A.1979. An algorithm for planning collision free paths among polyhedral obstacles. Comm. ACM22:560-570.
6.
Lyusternik, L.A.1964. Shortest paths, variational problems. New York: Pergamon Press.
7.
Mount, D.1985. On finding shortest paths on convex polyhedra. CAR-TR-120, University of Maryland.
8.
O'Rourke, J., Suri, S., and Booth, H.1985. Shortest paths on polyhedral surfaces. Proc. Symp. on Theoretical Aspects ofComputing, pp. 243-254.
9.
Papadimitriou, C.1985. An algorithm for shortest path motion in three dimensions . Information Processing Lett.20:259-263.
10.
Reif, J., and Storer, J.1985 (Waltham, Massachusetts). Shortest paths in Euclidean space with polyhedral obstacles. Computer Science Tech. Report, CS-85-121.
11.
Sharir, M., and Schorr, A.1984. On shortest paths in polyhedral spaces. Proc. 16th Symp. on the Theory ofComputing, pp. 144-153.
