Polytime algorithm for the shortest path in a homotopy class amidst semi-algebraic obstacles in the plane

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.

	AM88	M.E. Alonso and Raimondo M. The computation of the topology of a planar semialgebraic set. Rend. Sere. Mat. Univers. Politecn. TorinoF 46(3):327-342F 1988.
	BCR87	J. BochnakF M. CosteF and M.-F. Roy. Cdomdtrie algdbrique rdelle. Springer-VerlagF 1987.
	BSS89	L. BlumF M. SI~bF and S. Smale. On a theory of computation and complexity over real numbers: NP-completenessF recursi~ functions and universal machines. Bull. Amer. Math. Soc.F 1:1- 46F 1989.
	Can88	John F. Canny, The complexity of robot motion planning, MIT Press, Cambridge, MA, 1988
	CGV92	D. Yu. Grigor'ev , N. N. Vorobjov, Jr., Counting connected components of a semialgebraic set in subexponential time, Computational Complexity, v.2 n.2, p.133-186, 1992 [doi>10.1007/BF01202001]
	CR87	J. Canny and J. Reif. New lower bound technique for robot motion planning problemms. In Proc. 28th Annu. IEEE Syrup. on Foundations of Comput. Sci.F pages 49-60F 1987.
	CSY94	Joonsoo Choi , Jürgen Sellen , Chee-Keng Yap, Approximate Euclidean shortest path in 3-space, Proceedings of the tenth annual symposium on Computational geometry, p.41-48, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.177501]
	GHR+90	D. Yu. GrigorievF J. HeintzF M.-F. RoyF SolernSF and N. N. VorobjovF Jr. Comptage des composantes connexes d'un ensemble semialg~brique en temps simplement exponentiel. C. R. Acad. Sci. ParisF 311F Ser. 1:879-882F 1990.
	Gri88	D. Yu. Grigor'ev, Complexity of deciding Tarski algebra, Journal of Symbolic Computation, v.5 n.1-2, p.65-108, February/April 1988 [doi>10.1016/S0747-7171(88)80006-3]
	GS97	Dima Grigoriev , Anatol Slissenko, Computing Minimum-Link Path in a Homotopy Class amidst Semi-Algebraic Obstacles in the Plane, Proceedings of the 12th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.114-129, June 23-27, 1997
	GV88	D. Yu. Grigor'ev , N. N. Vorobjov, Solving systems of polynomial inequalities in subexponential time, Journal of Symbolic Computation, v.5 n.1-2, p.37-64, February/April 1988 [doi>10.1016/S0747-7171(88)80005-1]
	GV92	D. Yu. Grigor'ev , N. N. Vorobjov, Jr., Counting connected components of a semialgebraic set in subexponential time, Computational Complexity, v.2 n.2, p.133-186, 1992 [doi>10.1007/BF01202001]
	HKSS94	J. HeintzFT. KrickFA. SlissenkoF and P. Solernd. Search for shortest path around semialgebraic obstacles in the plane. J. Math. SciencesF 70(4):1944-1949F 1994. Translation into English of the paper published in Zapiski Nauchn. Semin. LOM1F ~ol. 192(1991)F p. 163-173.
	HRS90	J. HeintzF M.-F. RffF and P SolernS. Sur la complexit~ du principe de Tarski-Seidenberg. Bull. Soc. Math. de FranceF 118:101-126F 1990.
	HRS94	J. HeintzF M.-F. RffF and P SolernS. Description of the connected components of a semialgebraic set in single exponential time. Discrete and Computational CeometryF 11:121-140F 1994.
	HS94	John Hershberger , Jack Snoeyink, Computing minimum length paths of a given homotopy class, Computational Geometry: Theory and Applications, v.4 n.2, p.63-97, June 1994 [doi>10.1016/0925-7721(94)90010-8]
	Lat91	Jean-Claude Latombe, Robot Motion Planning, Kluwer Academic Publishers, Norwell, MA, 1991
	MS95	J.S.B. Mitchell and Suri S. A survey on computational geometryF volume 7 of Hanbooks in Operations Research and Management SciencesF chapter 7F pages 425-479. Elsevier Science B. V.F 1995.
	Pap85	C.H. Papadimitriou. An algorithm for shortestpath motion in three dimensions. Inform. Process. Lett.F 20:259-263F 1985.
	Pap94	C.H. Papadimitriou. Computational complexity. Addison-WesleyF 1994.
	Ren92	James Renegar, On the computational complexity and geometry of the first-order theory of the reals. Par I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals, Journal of Symbolic Computation, v.13 n.3, p.255-299, March 1992
	SS90	Jacob T. Schwartz , Micha Sharir, Algorithmic motion planning in robotics, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	ST80	H. Seifert and W. Threlefall. A Textbook of Topology. Academic PressF 1980.