{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:23:02Z","timestamp":1725664982982},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540631637"},{"type":"electronic","value":"9783540691938"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-63163-1_9","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T23:10:28Z","timestamp":1330297828000},"page":"114-129","source":"Crossref","is-referenced-by-count":2,"title":["Computing minimum-link path in a homotopy class amidst semi-algebraic obstacles in the plane"],"prefix":"10.1007","author":[{"given":"D.","family":"Grigoriev","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A.","family":"Slissenko","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,8]]},"reference":[{"issue":"3","key":"9_CR1","first-page":"327","volume":"46","author":"M. E. Alonso","year":"1988","unstructured":"M. E. Alonso and Raimondo M. The computation of the topology of a planar semialgebraic set. Rend. Sem. Mat. Univers. Politecn. Torino, 46(3):327\u2013342, 1988.","journal-title":"Rend. Sem. Mat. Univers. Politecn. Torino"},{"key":"9_CR2","unstructured":"J. Bochnak, M. Coste, and M.-F. Roy. G\u00e9om\u00e9trie alg\u00e9brique r\u00e9elle. Springer-Verlag, 1987."},{"key":"9_CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/S0273-0979-1989-15750-9","volume":"1","author":"L. Blum","year":"1989","unstructured":"L. Blum, M. Shub, and S. Smale. On a theory of computation and complexity over real numbers: NP-completeness, recursive functions and universal machines. Bull. Amer. Math. Soc., 1:1\u201346, 1989.","journal-title":"Bull. Amer. Math. Soc."},{"key":"9_CR4","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1006\/jagm.1995.1033","volume":"19","author":"V. Chandru","year":"1995","unstructured":"V. Chandru, S. K. Ghosh, A. Maheshwari, V. T. Rajan, and S. Saluja. NC-algorithms for minimum link path and related problems. J. of Algorithms, 19:173\u2013203, 1995.","journal-title":"J. of Algorithms"},{"key":"9_CR5","doi-asserted-by":"crossref","unstructured":"J. Canny and J. Reif. New lower bound technique for robot motion planning problemms. In Proc. 28th Annu. IEEE Symp. on Foundations of Comput. Sci., pages 49\u201360, 1987.","DOI":"10.1109\/SFCS.1987.42"},{"key":"9_CR6","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/S0747-7171(88)80006-3","volume":"5","author":"D. Y. Grigoriev","year":"1988","unstructured":"D. Yu. Grigoriev. Complexity of deciding Tarski algebra. J. Symb. Comput., 5:65\u2013108, 1988.","journal-title":"J. Symb. Comput."},{"issue":"2","key":"9_CR7","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/BF01202001","volume":"2","author":"D. Y. Grigoriev","year":"1992","unstructured":"D. Yu. Grigoriev and N. N. Vorobjov. Counting connected components of a semi-algebraic set in subexponential time. Computational Complexity, 2(2):133\u2013184, 1992.","journal-title":"Computational Complexity"},{"key":"9_CR8","first-page":"94","volume-title":"Publications du d\u00e9partement de math\u00e9matiques de l'Universit\u00e9 de Limoges","author":"J. Heintz","year":"1993","unstructured":"J. Heintz, T. Krick, A. Slissenko, and P. Solern\u00f3. Une borne inf\u00e9rieure pour la construction de chemins polygonaux dans R n . In Publications du d\u00e9partement de math\u00e9matiques de l'Universit\u00e9 de Limoges, pages 94\u2013100. Universit\u00e9 de Limoges, France, 1993."},{"issue":"4","key":"9_CR9","doi-asserted-by":"crossref","first-page":"1944","DOI":"10.1007\/BF02112433","volume":"70","author":"J. Heintz","year":"1994","unstructured":"J. Heintz, T. Krick, A. Slissenko, and P. Solern\u00f3. Search for shortest path around semialgebraic obstacles in the plane. J. Math. Sciences, 70(4):1944\u20131949, 1994. Translation into English of the paper published in Zapiski Nauchn. Semin. LOMI, vol. 192(1991), p. 163\u2013173.","journal-title":"J. Math. Sciences"},{"key":"9_CR10","doi-asserted-by":"crossref","first-page":"101","DOI":"10.24033\/bsmf.2138","volume":"118","author":"J. Heintz","year":"1990","unstructured":"J. Heintz, M.-F. Roy, and P. Solern\u00f3. Sur la complexit\u00e9 du principe de Tarski-Seidenberg. Bull. Soc. Math. de France, 118:101\u2013126, 1990.","journal-title":"Bull. Soc. Math. de France"},{"key":"9_CR11","doi-asserted-by":"crossref","unstructured":"J. Heintz, M.-F. Roy, and P. Solern\u00f3. Single exponential path finding in semi-algebraic sets. part 2: the general case. In Ch. L. Bajaj, editor, Algebraic Geometry and Its Applications, 1994.","DOI":"10.1007\/978-1-4612-2628-4_28"},{"key":"9_CR12","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/0925-7721(94)90010-8","volume":"4","author":"J. Hershberger","year":"1994","unstructured":"J. Hershberger and J. Snoeyink. Computing minimum length paths of a given homotopy class. Computational Geometry, 4:63\u201397, 1994.","journal-title":"Computational Geometry"},{"key":"9_CR13","doi-asserted-by":"crossref","unstructured":"J. S. B. Mitchell, C. Piatko, and E. M. Arkin. Computing a shortest k-link path in a polygon. In Proc. 33rd IEEE FOCS, pages 573\u2013582, 1992.","DOI":"10.1109\/SFCS.1992.267794"},{"key":"9_CR14","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1007\/BF01758855","volume":"8","author":"J. S. B. Mitchell","year":"1992","unstructured":"J. S. B. Mitchell, G. Rote, and G. Woeginger. Minimum-link paths among obstacles in the plane. Algorithmica 8:431\u2013459, 1992.","journal-title":"Algorithmica"},{"key":"9_CR15","doi-asserted-by":"crossref","unstructured":"J. S. B. Mitchell and Suri S. A survey on computational geometry, volume 7 of Hanbooks in Operations Research and Management Sciences, chapter 7, pages 425\u2013479. Elsevier Science B. V., 1995.","DOI":"10.1016\/S0927-0507(05)80124-0"},{"key":"9_CR16","unstructured":"C. H. Papadimitriou. Computational complexity. Addison-Wesley, 1994."},{"issue":"3","key":"9_CR17","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/S0747-7171(10)80003-3","volume":"13","author":"J. Renegar","year":"1992","unstructured":"J. Renegar. On the computational complexity and geometry of the first-order theory of the reals. parts 1\u20133. J. Symb. Comput., 13(3):255\u2013352, 1992.","journal-title":"J. Symb. Comput."},{"key":"9_CR18","unstructured":"H. Seifert and W. Threlfall. A Textbook of Topology. Academic Press, 1980."}],"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-63163-1_9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:16:17Z","timestamp":1605647777000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63163-1_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540631637","9783540691938"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-63163-1_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}