A single-exponential upper bound for finding shortest paths in three dimensions

ABSTRACT

We derive a single-exponential time upper bound for finding the shortest path between two points in 3-dimensional Euclidean space with (nonnecessarily convex) polyhedral obstacles. Prior to this work, the best known algorithm required double-exponential time. Given that the problem is known to be PSPACE-hard, the bound we present is essentially the best (in the worst-case sense) that can reasonably be expected.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	Takao Asano , Tetsuo Asano , Hiroshi Imai, Partitioning a polygonal region into trapezoids, Journal of the ACM (JACM), v.33 n.2, p.290-312, April 1986 [doi>10.1145/5383.5387]
	3	~BAJAJ, C. 1985. The algebraic complexity of shortest paths m polyhedral spaces. In Proceedings ~of the 23rd Allerton Conference.
	4	~B^JAJ, C. 1986. An efficmnt parallel solution for a Euclidean shortest path m three dimen- ~sions. In Proceedings of the IEEE International Conference on Robotzcs and Azttomatlon (San ~Francisco, Calif.). IEEE, New York.
	5	Avikam Balstan , Micha Sharir, On the shortest paths between two convex polyhedra, Journal of the ACM (JACM), v.35 n.2, p.267-287, April 1988 [doi>10.1145/42282.214094]
	6	Michael Ben-Or , Dexter Kozen , John Reif, The complexity of elementary algebra and geometry, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.457-464, December 1984 [doi>10.1145/800057.808712]
	7	~CANNY, J., AND REIF, J. 1987. New lower bound techniques for robot motion planning. In ~Proceedings o} the 28th IEEE Sympostum on tile Fottndattons of Conzpttter Sczence (Los Angeles, ~Calif.). IEEE, New York, pp. 49 60.
	8	~CmSTOV, A. L., AND GmGOR'EV, D. YU. 1985. Complexity of quantifier elimination in the ~theory of algebraically closed fields. Tech. Rep. Institute of the Academy of Science, Lemngrad, ~USSR.
	9	K. Clarkson, Approximation algorithms for shortest path motion planning, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.56-65, January 1987, New York, New York, United States [doi>10.1145/28395.28402]
	10	George E. Collins, Hauptvortrag: Quantifier elimination for real closed fields by cylindrical algebraic decomposition, Proceedings of the 2nd GI Conference on Automata Theory and Formal Languages, p.134-183, May 20-23, 1975
	11	~FRANKLIN, W. R., AND AKMAN, V. 1984. Mimmal paths between two points on/around a ~convex polyhedron. Tech. Rep. Electrical, Computer, and Systems Engineering Dept., Rensse- ~laer Polytechnic Institute, Troy, N.Y.
	12	~FRANKLIN, W. R., AKMAN, V., AND VERmLt,~, C. 1984. Voroni diagrams with barriers and on ~polyhedra. Tech. Rep. Electrical, Computer, and Systems Engineering Dept., Rensselaer ~Polytechnic Institute, Troy, N.Y.
	13	JOHNSON, D.S. 1982. The column of NP-completeness. J. Algorithms 3, 182-195.
	14	~KEIL, J.M. 1983. Decomposing polygons into simpler components. Ph.D. dissertation. Tech. ~Rep. 163/83. Dept. of Computer Science, Univ. Toronto, Toronto, Ont., Canada.
	15	Andrzej Lingas, The Power of Non-Rectilinear Holes, Proceedings of the 9th Colloquium on Automata, Languages and Programming, p.369-383, July 12-16, 1982
	16	Anna Lubiw, Decomposing polygonal regions into convex quadrilaterals, Proceedings of the first annual symposium on Computational geometry, p.97-106, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323247]
	17	Joseph S. B. Mitchell , David M. Mount , Christos H. Papadimitriou, The discrete geodesic problem, SIAM Journal on Computing, v.16 n.4, p.647-668, Aug. 1987 [doi>10.1137/0216045]
	18	~O'ROURKE, J., SUR1, S., AND BOOTIt, H. 1984. Shortest paths on polyhedral surfaces. Tech. ~Rep. Dept. of Electrical Engineering and Computer Science. Johns Hopkins Univ., Baltimore, ~Md.
	19	~PAPADIMITRIOU, C.H. 1985. An algorithm for shortest-path motion in three dimensions, lnf ~Proc. Lett. 20, 259-263.
	20	~REIF, J., AND SHARIR. M. 1984. Motion planning in the presence of moving obstacles. Tech. ~Rep. TR-06-85. Aiken Computation Laboratory, Harvard Univ.
	21	A Sharir , A Baltsan, On shortest paths amidst convex polyhedra, Proceedings of the second annual symposium on Computational geometry, p.193-206, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10537]
	22	Micha Sharir( , Amir Schorr, On shortest paths in polyhedral spaces, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.144-153, December 1984 [doi>10.1145/800057.808676]