{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T01:58:03Z","timestamp":1760061483819},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540545224"},{"type":"electronic","value":"9783540384366"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1991]]},"DOI":"10.1007\/3-540-54522-0_99","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T17:59:54Z","timestamp":1330192794000},"page":"94-107","source":"Crossref","is-referenced-by-count":7,"title":["Computing roadmaps of general semi-algebraic sets"],"prefix":"10.1007","author":[{"given":"J. F.","family":"Canny","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"9_CR1","series-title":"Ergebnisse der mathematik","volume-title":"G\u00e9om\u00e9trie alg\u00e9brique r\u00e9elle","author":"J. Bochnak","year":"1987","unstructured":"J. Bochnak, M. Coste, and M-F. Roy. G\u00e9om\u00e9trie alg\u00e9brique r\u00e9elle. Number 12 in Ergebnisse der mathematik 3. Springer-Verlag, Berlin, 1987."},{"key":"9_CR2","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/0022-0000(86)90029-2","volume":"32","author":"M. Ben-Or","year":"1986","unstructured":"M. Ben-Or, D. Kozen, and J. Reif. The complexity of elementary algebra and geometry. J. Comp. and Sys. Sci., 32:251\u2013264, 1986.","journal-title":"J. Comp. and Sys. Sci."},{"key":"9_CR3","volume-title":"The Complexity of Robot Motion Planning","author":"J.F. Canny","year":"1988","unstructured":"J.F. Canny. The Complexity of Robot Motion Planning. M.I.T. Press, Cambridge, 1988."},{"key":"9_CR4","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/0004-3702(88)90055-0","volume":"37","author":"J.F. Canny","year":"1988","unstructured":"J.F. Canny. Constructing roadmaps of semi-algebraic sets I: Completeness. Artificial Intelligence, 37:203\u2013222, 1988.","journal-title":"Artificial Intelligence"},{"key":"9_CR5","doi-asserted-by":"crossref","unstructured":"J.F. Canny. Some algebraic and geometric computations in PSPACE. In ACM Symposium on Theory of Computing, pages 460\u2013467, 1988.","DOI":"10.1145\/62212.62257"},{"key":"9_CR6","series-title":"Technical report","volume-title":"Computing roadmaps of semi-algebraic sets","author":"J.F. Canny","year":"1990","unstructured":"J.F. Canny. Computing roadmaps of semi-algebraic sets. Technical report, University of California, Berkeley, 1990."},{"key":"9_CR7","doi-asserted-by":"crossref","unstructured":"J.F. Canny. An improved sign determination algorithm. In AAECC-91 (this volume), 1991.","DOI":"10.1007\/3-540-54522-0_100"},{"key":"9_CR8","doi-asserted-by":"crossref","unstructured":"J.F. Canny, D.Y. Grigor'ev, and N.N. Vorobjov. Finding connected components of a semialgebraic set in subexponential time. App. Algebra in Eng. Comm. and Comp. (submitted), 1991.","DOI":"10.1007\/BF01614146"},{"key":"9_CR9","unstructured":"N. Fitchas, A. Galligo, and J. Morgenstern. Algorithmes rapides en s\u00e9quential et en parall\u00e8le pour l'\u00e9limination des quantificateur en g\u00e9om\u00e9trie \u00e9l\u00e9mentaire. S\u00e9m. Structures Alg\u00e9briques Ordonn\u00e9es, 1987."},{"key":"9_CR10","unstructured":"L. Gournay. Construction of roadmaps in semialgebraic sets. manuscript, 1991."},{"key":"9_CR11","unstructured":"D.Y. Grigor'ev and N.N. Vorobjov. Counting connected components of a semialgebraic set in subexponential time. Computational Complexity (submitted), 1989."},{"key":"9_CR12","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0095244","volume-title":"Topological Stability of Smooth Mappings","author":"C.G. Gibson","year":"1976","unstructured":"C.G. Gibson, K. Wirthm\u00fcller, A.A. Du Plessis, and E.J.N. Looijenga. Topological Stability of Smooth Mappings. Number 552 in Lecture Notes in Mathematics. Springer-Verlag, New York, 1976."},{"key":"9_CR13","doi-asserted-by":"crossref","unstructured":"J. Heintz, M.F. Roy, and P. Solerno. Single-exponential path finding in semialgebraic sets I: The case of a smooth bounded hypersurface. In AAECC-90, Springer LNCS (to appear), 1990.","DOI":"10.1007\/3-540-54195-0_50"},{"key":"9_CR14","unstructured":"J. Heintz, M.F. Roy, and P. Solerno. Single-exponential path finding in semialgebraic sets II: The general case. In To appear Proc. 60th Birthday Conf. for S. Abhyankar, 1990."},{"key":"9_CR15","doi-asserted-by":"crossref","unstructured":"D. Kozen and C. Yap. Algebraic cell decomposition in NC. In IEEE Conference on Foundations of Computer Science, pages 515\u2013521, 1985.","DOI":"10.1109\/SFCS.1985.4"},{"key":"9_CR16","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1016\/0196-8858(83)90014-3","volume":"4","author":"J.T. Schwartz","year":"1983","unstructured":"J.T. Schwartz and M. Sharir. On the piano movers' problem, II: General techniques for computing topological properties of real algebraic manifolds. Advances in Applied Mathematics, 4:298\u2013351, 1983.","journal-title":"Advances in Applied Mathematics"},{"key":"9_CR17","unstructured":"D. Trotman. On Canny's roadmap algorithm: Orienteering in semialgebraic sets. Technical report, Univ. Aix-Marseille, 1989."}],"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-54522-0_99.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T15:55:32Z","timestamp":1605628532000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-54522-0_99"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991]]},"ISBN":["9783540545224","9783540384366"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-54522-0_99","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1991]]}}}