{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:56:51Z","timestamp":1725663411961},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540516835"},{"type":"electronic","value":"9783540467489"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/3-540-51683-2_24","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T16:12:15Z","timestamp":1330186335000},"page":"49-66","source":"Crossref","is-referenced-by-count":1,"title":["The algorithm by schwartz, sharir and collins on the piano mover's problem"],"prefix":"10.1007","author":[{"given":"Jo\u00ebl","family":"Marchand","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"4_CR1","doi-asserted-by":"crossref","unstructured":"D.S. Arnon, B. Buchberger, Algorithms in Real Algebraic Geometry, Reprinted from the Journal of Symbolic Computation, vol 5, number 1\u20132, Academic Press, 1988.","DOI":"10.1016\/S0747-7171(88)80002-6"},{"key":"4_CR2","volume-title":"Calcul formel: syst\u00e8mes et algorithmes de manipulations alg\u00e9briques","author":"J. Davenport","year":"1987","unstructured":"J. Davenport, Y. Siret, E. Tournier, Calcul formel: syst\u00e8mes et algorithmes de manipulations alg\u00e9briques, Masson, Paris, 1987."},{"key":"4_CR3","volume-title":"G\u00e9om\u00e9trie alg\u00e9brique r\u00e9elle","author":"J. Bochnak","year":"1987","unstructured":"J. Bochnak, M. Coste, M-F. Roy, G\u00e9om\u00e9trie alg\u00e9brique r\u00e9elle, Springer-Verlag, Berlin, 1987."},{"key":"4_CR4","volume-title":"Computer algebra. Symbolic and Algebraic Computation","author":"B. Buchberger","year":"1982","unstructured":"B. Buchberger, G.E. Collins, R. Loos, Computer algebra. Symbolic and Algebraic Computation, Springer-Verlag, New-York, 1982."},{"key":"4_CR5","unstructured":"J. Della-Dora, M-F. Roy, J-J. Risler, Calcul Formel et outils alg\u00e9briques pour la mod\u00e9lisation g\u00e9om\u00e9trique, Actes du S\u00e9minaire, CNRS, 1988."},{"key":"4_CR6","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1007\/3-540-07407-4_17","volume":"33","author":"G.E. Collins","year":"1975","unstructured":"G.E. Collins, Quantifier elimination for real closed fields by Cylindrical Algebraic Decomposition, Lecture Notes in Comp. Sc., vol 33, pp 134\u2013183, Springer-Verlag, 1975.","journal-title":"Lecture Notes in Comp. Sc."},{"key":"4_CR7","doi-asserted-by":"crossref","first-page":"865","DOI":"10.1137\/0213054","volume":"13","author":"D.S. Arnon","year":"1984","unstructured":"D.S. Arnon, G.E. Collins, S. Mc Callum, Cylindrical Algebraic Decomposition I: the basic algorithm, SIAM J. Computations, vol 13, pp 865\u2013877, 1984.","journal-title":"SIAM J. Computations"},{"key":"4_CR8","doi-asserted-by":"crossref","first-page":"878","DOI":"10.1137\/0213055","volume":"13","author":"D.S. Arnon","year":"1984","unstructured":"D.S. Arnon, G.E. Collins, S. Mc Callum, Cylindrical Algebraic Decomposition II: an adjacency algorithm for the plane, SIAM J. Computations, vol 13, pp 878\u2013889, 1984.","journal-title":"SIAM J. Computations"},{"key":"4_CR9","unstructured":"S. Mc Callum, An improved projection operator for Cylindrical Algebraic Decomposition, Ph.D. Thesis, University of Wisconsin-Madison, 1984."},{"key":"4_CR10","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1007\/3-540-15984-3_272","volume":"204","author":"D.S. Arnon","year":"1985","unstructured":"D.S. Arnon, G.E. Collins, S. Mc Callum, An adjacency algorithm for Cylindrical Algebraic Decompositions of three-dimensional space, Proc. EUROCAL 85 Vol. 2, Lecture Notes in Computer Science, vol 204, pp 246\u2013261, Springer-Verlag, 1985.","journal-title":"Lecture Notes in Computer Science"},{"key":"4_CR11","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1007\/3-540-15984-3_273","volume":"204","author":"D.S. Arnon","year":"1985","unstructured":"D.S. Arnon, A cluster-based cylindrical algebraic decomposition algorithm, Proc. EUROCAL 85 Vol. 2, Lecture Notes in Computer Science, vol 204, pp 262\u2013269, Springer-Verlag, 1985.","journal-title":"Lecture Notes in Computer Science"},{"key":"4_CR12","unstructured":"A. Paugam, Comparaison entre trois algorithmes d'\u00e9limination des quantificateurs sur les corps r\u00e9els clos, Th\u00e8se de troisi\u00e8me cycle, Universit\u00e9 de Rennes I, 1986."},{"key":"4_CR13","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/S0747-7171(88)80008-7","volume":"5","author":"M. Coste","year":"1988","unstructured":"M. Coste, M-F. Coste-Roy, Thom's lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets, Journal of Symbolic Computation, vol 5, number 1\u20132, pp 121\u2013129, Academic Press,1988.","journal-title":"Journal of Symbolic Computation"},{"key":"4_CR14","unstructured":"M-F. Roy, Computation of the topology of a real curve, IRMAR, Universit\u00e9 de Rennes I."},{"key":"4_CR15","unstructured":"M-F. Roy, Aviva Szpirglas, Complexity of the computation on real algebraic numbers, IRMAR, Universit\u00e9 de Rennes I, to appear."},{"key":"4_CR16","volume-title":"Computer algebra for Cylindrical Algebraic Decomposition","author":"J. Davenport","year":"1985","unstructured":"J. Davenport, Computer algebra for Cylindrical Algebraic Decomposition, TRITA-NA-8511, NADA, KTH, Stockholm, 1985."},{"key":"4_CR17","unstructured":"J-J. Risler, About the piano mover's problem, Universit\u00e9 de Paris VI, to appear."},{"key":"4_CR18","unstructured":"M. Merle, Le probl\u00e8me du d\u00e9m\u00e9nageur, Ecole Polytechnique, Palaiseau, 1987."},{"key":"4_CR19","doi-asserted-by":"crossref","unstructured":"J.T. Schwartz, M. Sharir, On the piano mover's problem, I, II, III, V, Comm. Pure Appl. Math, vol 36 & 37, 1983 & 1984 et Adv. Appl. math., vol 4, 1983.","DOI":"10.1002\/cpa.3160360103"},{"key":"4_CR20","unstructured":"E. Ariel-Sheffi, M. Sharir, On the piano mover's problem, IV, Comm. Pure Appl. Math, vol 37, 1984."},{"key":"4_CR21","doi-asserted-by":"crossref","unstructured":"M. Sharir, S. Sifroni, A new efficient motion planning algorithm for a rod in polygonal space, ACM, 1986.","DOI":"10.1145\/10515.10535"},{"key":"4_CR22","unstructured":"F. Ollivier, Implantation d'un algorithme de M. Sharir et S. Sifroni pour le d\u00e9placement d'une tige dans un espace polygonal, Universit\u00e9 de Paris VI, Rapport de DEA-LAP, 1987."},{"key":"4_CR23","unstructured":"O'Dunlaing, Yap, The Voron\u00ef method for motion planning: I. The case of a disc, Robotics Research, Technical Reports, Courant Institute, N.Y. University, 1983."},{"key":"4_CR24","unstructured":"O'Dunlaing, M. Sharir, Yap, Generalized Vorono\u00ef diagrams for motion a ladder: I, II, Robotics Research, Technical Reports, Courant Institute, N.Y. University, 1984."},{"key":"4_CR25","unstructured":"R. Loos, The Algorithmic Description Language: ALDES, Universit\u00e4t 675, Kaiserslautern."},{"key":"4_CR26","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1145\/14956.14958","volume":"20.4","author":"L. Langemyr","year":"1986","unstructured":"L. Langemyr, Converting SAC2-Code to Lisp, SIGSAM Bulletin, vol 20.4, pp 11\u201313, 1986.","journal-title":"SIGSAM Bulletin"},{"key":"4_CR27","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1007\/BFb0032837","volume":"174","author":"R.D. Jenks","year":"1984","unstructured":"R.D. Jenks, A primer: 11 keys for a new SCRATCHPAD, Proc. EUROSAM 84, Lecture Notes in Computer Science, vol 174, pp 123\u2013147, Springer-Verlag, 1984.","journal-title":"Lecture Notes in Computer Science"},{"key":"4_CR28","unstructured":"M-C. Gontard, Une premi\u00e8re approche de la s\u00e9mantique du langage de calcul formel Scratchpad II, Universit\u00e9 de Paris VI, Rapport de DEA-LAP, 1987."},{"key":"4_CR29","doi-asserted-by":"crossref","unstructured":"J. Della-Dora, C. Dicrescenzo, D. Duval, About a new method for computing in algebraic number fields, Proc. EUROCAL 85 Vol.2, Lecture Notes in Computer Science, vol 204, pp 289\u2013290, Springer-Verlag, 1985.","DOI":"10.1007\/3-540-15984-3_279"},{"key":"4_CR30","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1145\/12917.12919","volume":"20.1&2","author":"J. Davenport","year":"1986","unstructured":"J. Davenport, A \u201cpiano mover's\u201d problem, SIGSAM Bulletin, vol 20.1&2, pp 15\u201317, 1986.","journal-title":"SIGSAM Bulletin"},{"issue":"1\u20132","key":"4_CR31","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/S0747-7171(88)80015-4","volume":"5","author":"D. Lazard","year":"1988","unstructured":"D. Lazard, Quantifier elimination: optimal solutions for two classical examples, Journal of Symbolic Computation, vol 5, number 1\u20132, pp 261\u2013266, Academic Press, 1988.","journal-title":"Journal of Symbolic Computation"},{"key":"4_CR32","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1007\/3-540-15984-3_274","volume":"204","author":"D.S. Arnon","year":"1985","unstructured":"D.S. Arnon, On mechanical quantifier elimination for elementary algebra and geometry: solution of a nontrivial problem, Proc. EUROCAL 85 Vol. 2, Lecture Notes in Computer Science, vol 204, pp 270\u2013271, Springer-Verlag, 1985.","journal-title":"Lecture Notes in Computer Science"},{"key":"4_CR33","volume-title":"Commande nodale par retour statique de sortie: m\u00e9thode alg\u00e9brique","author":"C. Champetier","year":"1987","unstructured":"C. Champetier, J-F. Magni, Commande nodale par retour statique de sortie: m\u00e9thode alg\u00e9brique, Rapport C.E.R.T, Toulouse, 1987."},{"key":"4_CR34","unstructured":"A. Ben Cherifa, Preuves de terminaison des syst\u00e8mes de r\u00e9\u00e9criture. Un outil fond\u00e9 sur les interpr\u00e9tations polynomiales, Th\u00e8se de doctorat, Universit\u00e9 de Nancy I, 1986."}],"container-title":["Lecture Notes in Computer Science","Geometry and Robotics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-51683-2_24.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:22:22Z","timestamp":1605630142000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-51683-2_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540516835","9783540467489"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/3-540-51683-2_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]}}}