{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T11:49:40Z","timestamp":1776685780277,"version":"3.51.2"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540541950","type":"print"},{"value":"9783540474890","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1991]]},"DOI":"10.1007\/3-540-54195-0_50","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T22:35:17Z","timestamp":1330209317000},"page":"180-196","source":"Crossref","is-referenced-by-count":8,"title":["Single exponential path finding in semialgebraic sets Part I: The case of a regular bounded hypersurface"],"prefix":"10.1007","author":[{"given":"Joos","family":"Heintz","sequence":"first","affiliation":[]},{"given":"Marie-Francoise","family":"Roy","sequence":"additional","affiliation":[]},{"given":"Pablo","family":"Solern\u00f3","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,8]]},"reference":[{"key":"17_CR1","unstructured":"Bochnak J., Coste M., Roy M.-F.: G\u00e9om\u00e9trie alg\u00e9brique r\u00e9elle. Springer Verlag (1987)."},{"key":"17_CR2","doi-asserted-by":"crossref","unstructured":"Canny J: Some algebraic and geometric computations in PSPACE. ACM Symptosium on the theory of computation, 460\u2013467 (1988).","DOI":"10.1145\/62212.62257"},{"key":"17_CR3","unstructured":"Canny J.: The complexity of motion planning. M.I.T. Thesis 1986, M.I.T. Press (1988)."},{"key":"17_CR4","doi-asserted-by":"crossref","unstructured":"Canny J.: A new algebraic method for robot motion planning and real geometry. Proc. 28th IEEE Symp. on Found. of Comp. Science (FOCS), 39\u201348 (1987).","DOI":"10.1109\/SFCS.1987.1"},{"key":"17_CR5","unstructured":"Canny J., Grigor'ev D., Vorobjov N.: Defining connected components of a semialgebraic set in subexponential time. Manuscript Steklov Mathematical Inst., Leningrad, LOMI (1990)."},{"key":"17_CR6","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/S0747-7171(88)80008-7","volume":"5","author":"M. Coste","year":"1988","unstructured":"Coste M., Roy M.-F.: Thom's lemma, the coding of real algebraic numbers and the topology of semialgebraic sets. J. Symbolic Computation 5, 121\u2013129 (1988).","journal-title":"J. Symbolic Computation"},{"issue":"32","key":"17_CR7","first-page":"29","volume":"VII","author":"N. Fitchas","year":"1990","unstructured":"Fitchas N., Galligo A., Morgenstern J.: Algorithmes rapides en s\u00e9quentiel et en parall\u00e8le pour l'\u00e9limination des quantificateurs en g\u00e9om\u00e9trie \u00e9l\u00e9mentaire. S\u00e9m. Structures Alg\u00e9briques Ordonn\u00e9es, S\u00e9lection d'expos\u00e9s 1984\u20131987 Vol I. Publ. Univ. Paris VII, No. 32, 29\u201335 (1990).","journal-title":"Publ. Univ. Paris"},{"key":"17_CR8","doi-asserted-by":"crossref","unstructured":"von zur Gathen J.: Parallel arithmetic computations; a survey. Proc. 13th Conf. MFCS (1986).","DOI":"10.1007\/BFb0016236"},{"key":"17_CR9","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/S0747-7171(88)80006-3","volume":"5","author":"D. Grigor'ev","year":"1988","unstructured":"Grigor'ev D.: Complexity of deciding Tarski algebra. J. Symbolic Computation 5, 65\u2013108 (1988).","journal-title":"J. Symbolic Computation"},{"key":"17_CR10","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/S0747-7171(88)80005-1","volume":"5","author":"D. Grigor'ev","year":"1988","unstructured":"Grigor'ev D., Vorobjov N.: Solving systems of polynomial inequalities in subexponential time. J. Symbolic Computation 5, 37\u201364 (1988).","journal-title":"J. Symbolic Computation"},{"key":"17_CR11","unstructured":"Grigor'ev D., Vorobjov N.: Counting connected components of a semialgebraic set in subexponential time. Manuscript Steklov Mathematica Inst., Leningrad, LOMI (1990)."},{"key":"17_CR12","unstructured":"Grigor'ev D., Heintz J., Roy M.-F., Solern\u00f3 P., Vorobjov N.: Comptage des composantes connexes d'un ensemble semi-alg\u00e9brique en temps simplement exponentiel. To appear in C.R. Acad. Sci. Paris."},{"key":"17_CR13","first-page":"293","volume":"89","author":"J. Heintz","year":"1989","unstructured":"Heintz J., Roy M.-F., Solern\u00f3 P.: On the complexity of semialgebraic sets. Proc. IFIP'89, 293\u2013298 (1989).","journal-title":"Proc. IFIP'"},{"key":"17_CR14","first-page":"825","volume":"309","author":"J. Heintz","year":"1989","unstructured":"Heintz J., Roy M.-F., Solern\u00f3 P.: Complexit\u00e9 du principe de Tarski-Seidenberg. Comptes Rendus de l'Acad. de Sciences Paris, 309, 825\u2013830 (1989).","journal-title":"Comptes Rendus de l'Acad. de Sciences Paris"},{"key":"17_CR15","doi-asserted-by":"crossref","first-page":"101","DOI":"10.24033\/bsmf.2138","volume":"118","author":"J. Heintz","year":"1990","unstructured":"Heintz J., Roy M.-F., Solern\u00f3 P.: Sur la complexit\u00e9 du principe de Tarski-Seidenberg. Bulletin de la Soc. Math. de France 118, 101\u2013126 (1990).","journal-title":"Bulletin de la Soc. Math. de France"},{"key":"17_CR16","unstructured":"Heintz J., Roy M.-F., Solern\u00f3 P.: Construction de chemins dans un ensemble semi-alg\u00e9brique (II). Preprint (1990)."},{"key":"17_CR17","doi-asserted-by":"crossref","unstructured":"Heintz J., Krick T., Roy M.-F., Solern\u00f3 P.: Geometric problems solvable in single exponential time. Preprint (1990).","DOI":"10.1007\/3-540-54195-0_35"},{"key":"17_CR18","unstructured":"Renegar J.: On the computational complexity and geometry of the first order theory of the reals. Technical Report 856, Cornell Univ. (1989)."},{"key":"17_CR19","unstructured":"Roy M.-F., Szpirglas A.: Sign determination on 0-dimensional sets. To appear in Proc. MEGA'90, Castiglioncello (1990)."},{"key":"17_CR20","doi-asserted-by":"crossref","unstructured":"Schwartz J., Sharir M.: On the piano movers' problem: II General Techniques for calculating topological properties of real algebraic manifolds. Adv. Appl. Math. 298\u2013351 (1983).","DOI":"10.1016\/0196-8858(83)90014-3"},{"key":"17_CR21","unstructured":"Solern\u00f3 P.: Complejidad de conjuntos semialgebraicos. Thesis Univ. de Buenos Aires (1989)."},{"key":"17_CR22","unstructured":"Solern\u00f3 P.: Construction de fonctions de Morse pour une hypersurface r\u00e9guli\u00e8re en temps admissible. Preprint (1990)."},{"key":"17_CR23","unstructured":"Trotman D.: On Canny's roadmap algorithm: orienteering in semialgebraic sets. Manuscript Univ. Aix-Marseille (1989)."},{"key":"17_CR24","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1137\/0212043","volume":"12","author":"L. Valiant","year":"1983","unstructured":"Valiant L., Skyum S., Berkowitz S., Rackoff C.: Fast parallel computation of polynomials using few processors. SIAM J. Comp. 12, 641\u2013644 (1983).","journal-title":"SIAM J. Comp."}],"container-title":["Lecture Notes in Computer Science","Applied Algebra, Algebraic Algorithms and Error-Correcting Codes"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-54195-0_50.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:52:58Z","timestamp":1605646378000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-54195-0_50"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991]]},"ISBN":["9783540541950","9783540474890"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-54195-0_50","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991]]}}}