{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:59:40Z","timestamp":1725487180422},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540441809"},{"type":"electronic","value":"9783540457497"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45749-6_38","type":"book-chapter","created":{"date-parts":[[2007,7,4]],"date-time":"2007-07-04T15:42:44Z","timestamp":1183563764000},"page":"411-423","source":"Crossref","is-referenced-by-count":7,"title":["Computing Homotopic Shortest Paths Efficiently"],"prefix":"10.1007","author":[{"given":"Alon","family":"Efrat","sequence":"first","affiliation":[]},{"given":"Stephen G.","family":"Kobourov","sequence":"additional","affiliation":[]},{"given":"Anna","family":"Lubiw","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,8,29]]},"reference":[{"issue":"4","key":"38_CR1","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1142\/S0218195994000252","volume":"4","author":"R. Bar-Yehuda","year":"1994","unstructured":"R. Bar-Yehuda and B. Chazelle. Triangulating disjoint Jordan chains. International Journal of Computational Geometry & Applications, 4(4):475\u2013481, 1994.","journal-title":"International Journal of Computational Geometry & Applications"},{"key":"38_CR2","doi-asserted-by":"crossref","unstructured":"S. Cabello, Y. Liu, A. Mantler, and J. Snoeyink. Testing homotopy for paths in the plane. In 18th Annual Symposium on Computational Geometry, pages 160\u2013169, 2002.","DOI":"10.1145\/513400.513421"},{"key":"38_CR3","doi-asserted-by":"crossref","unstructured":"B. Chazelle. A theorem on polygon cutting with applications. In 23rd Annual Symposium on Foundations of Computer Science, pages 339\u2013349, 1982.","DOI":"10.1109\/SFCS.1982.58"},{"key":"38_CR4","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/BF01762115","volume":"3","author":"B. Chazelle","year":"1988","unstructured":"B. Chazelle. An algorithm for segment-dragging and its implementation. Algorithmica, 3:205\u2013221, 1988.","journal-title":"Algorithmica"},{"key":"38_CR5","doi-asserted-by":"crossref","unstructured":"R. Cole and A. Siegel. River routing every which way, but loose. In 25th Annual Symposium on Foundations of Computer Science, pages 65\u201373, 1984.","DOI":"10.1109\/SFCS.1984.715902"},{"key":"38_CR6","doi-asserted-by":"crossref","unstructured":"M. deBerg, M. vanKreveld, M. H. Overmars, and O. Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, 2nd edition, 2000.","DOI":"10.1007\/978-3-662-04245-8"},{"key":"38_CR7","doi-asserted-by":"crossref","unstructured":"C. A. Duncan, A. Efrat, S. G. Kobourov, and C. Wenk. Drawing with fat edges. In 9th Symposium on Graph Drawing (GD\u201901), pages 162\u2013177, September 2001.","DOI":"10.1007\/3-540-45848-4_14"},{"key":"38_CR8","first-page":"34","volume":"15","author":"H. Edelsbrunner","year":"1981","unstructured":"H. Edelsbrunner. A note on dynamic range searching. Bulletin of the European Association for Theoretical Computer Science, 15:34\u201340, Oct. 1981.","journal-title":"Bulletin of the European Association for Theoretical Computer Science"},{"key":"38_CR9","doi-asserted-by":"crossref","unstructured":"A. Efrat, S. Kobourov, and A. Lubiw. Computing homotopic shortest paths efficiently. Technical report, April 2002. http:\/\/www.arXiv.org\/abs\/cs\/0204050 .","DOI":"10.1007\/3-540-45749-6_38"},{"key":"38_CR10","doi-asserted-by":"crossref","unstructured":"A. Efrat, S. G. Kobourov, M. Stepp, and C. Wenk. Growing fat graphs. In 18th Annual Symposium on Computational Geometry, pages 277\u2013278, 2002.","DOI":"10.1145\/513400.513434"},{"key":"38_CR11","doi-asserted-by":"crossref","unstructured":"S. Gao, M. Jerrum, M. Kaufmann, K. Mehlhorn, W. R\u00fclling, and C. Storb. On continuous homotopic one layer routing. In 4th Annual Symposium on Computational Geometry, pages 392\u2013402, 1988.","DOI":"10.1145\/73393.73433"},{"key":"38_CR12","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/0925-7721(94)90010-8","volume":"4","author":"Hershberger","year":"1994","unstructured":"Hershberger and Snoeyink. Computing minimum length paths of a given homotopy class. CGTA: Computational Geometry: Theory and Applications, 4:63\u201397, 1994.","journal-title":"CGTA: Computational Geometry: Theory and Applications"},{"issue":"3","key":"38_CR13","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1002\/net.3230140304","volume":"14","author":"D. T. Lee","year":"1984","unstructured":"D. T. Lee and F. P. Preparata. Euclidean shortest paths in the presence of rectilinear barriers. Networks, 14(3):393\u2013410, 1984.","journal-title":"Networks"},{"key":"38_CR14","doi-asserted-by":"crossref","unstructured":"C. E. Leiserson and F. M. Maley. Algorithms for routing and testing routability of planar VLSI layouts. In 17th Annual ACM Symposium on Theory of Computing, pages 69\u201378, 1985.","DOI":"10.1145\/22145.22153"},{"key":"38_CR15","unstructured":"J. S. B. Mitchell. Geometric shortest paths and network optimization. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry. 1998."},{"key":"38_CR16","volume-title":"The Design and Analysis of Spatial Data Structures","author":"H. Samet","year":"1989","unstructured":"H. Samet. The Design and Analysis of Spatial Data Structures. Addison-Wesley, Reading, MA, 1989."}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA 2002"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45749-6_38","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,30]],"date-time":"2019-04-30T03:06:28Z","timestamp":1556593588000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45749-6_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540441809","9783540457497"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-45749-6_38","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}