{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T15:45:44Z","timestamp":1725551144615},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540633075"},{"type":"electronic","value":"9783540694229"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-63307-3_64","type":"book-chapter","created":{"date-parts":[[2010,4,5]],"date-time":"2010-04-05T19:22:48Z","timestamp":1270495368000},"page":"248-257","source":"Crossref","is-referenced-by-count":2,"title":["On geometric path query problems"],"prefix":"10.1007","author":[{"given":"Danny Z.","family":"Chen","sequence":"first","affiliation":[]},{"given":"Ovidiu","family":"Daescu","sequence":"additional","affiliation":[]},{"given":"Kevin S.","family":"Klenk","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,7,30]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"N. M. Amato, M. T. Goodrich, and E. A. Ramos. Computing faces in segment and simplex arrangments. In Proceedings of the 27th Annual Symposium on the Theory of Computing. ACM, 29 May-1 June 1995.","key":"22_CR1","DOI":"10.1145\/225058.225285"},{"doi-asserted-by":"crossref","unstructured":"E. M. Arkin, R. Connelly, and J. S. B. Mitchell. On monotone paths among obstacles, with applications to planning assemblies. In Proceedings of the 5th Annual Symposium on Computational Geometry, pages 334\u2013343. ACM, June 1989.","key":"22_CR2","DOI":"10.1145\/73833.73870"},{"unstructured":"O. Berkman and U. Vishkin. Finding level-ancestors in trees. Technical Report UMIACS-TR-91-9, University of Maryland, 1991.","key":"22_CR3"},{"doi-asserted-by":"crossref","unstructured":"D. Z. Chen, K. S. Klenk, and H.-Y. T. Tu. Shortest path queries among weighted obstacles in the rectilinear plane. In Proceedings of the Eleventh Annual Symposium on Computational Geometry, pages 370\u2013379. ACM, 5\u20137 June 1995.","key":"22_CR4","DOI":"10.1145\/220279.220319"},{"unstructured":"K. L. Clarkson, S. Kapoor, and P. M. Vaidya. Rectilinear shortest paths through polygonal obstacles in O(n log 32 n) time. Unpublished manuscript.","key":"22_CR5"},{"doi-asserted-by":"crossref","unstructured":"K. L. Clarkson, S. Kapoor, and P. M. Vaidya. Rectilinear shortest paths through polygonal obstacles in O(n(log n)2) time. In Proceedings of the 3rd Annual Symposium on Computational Geometry, pages 251\u2013257. ACM, June 1987.","key":"22_CR6","DOI":"10.1145\/41958.41985"},{"doi-asserted-by":"crossref","unstructured":"J. Hershberger and S. Suri. Efficient computation of Euclidean shortest paths in the plane. In Proceedings of the 34th Annual Symposium on Foundations of Computer Science, pages 508\u2013517. IEEE, 3\u20135 Nov. 1993.","key":"22_CR7","DOI":"10.1109\/SFCS.1993.366836"},{"unstructured":"J. Hershberger and S. Suri. An optimal algorithm for Euclidean shortest paths in the plane. Manuscript, Feb. 1996.","key":"22_CR8"},{"unstructured":"J. Hershberger and S. Suri. Shortest path problems. Manuscript, 1996.","key":"22_CR9"},{"issue":"2","key":"22_CR10","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1142\/S0218195991000104","volume":"1","author":"D. T. Lee","year":"1991","unstructured":"D. T. Lee, C. D. Yang, and T. H. Chen. Shortest rectilinear paths among weighted obstacles. International Journal of Computational Geometry & Applications, 1(2):109\u2013124, 1991.","journal-title":"International Journal of Computational Geometry & Applications"},{"unstructured":"J. S. B. Mitchell. Shortest paths and networks. To appear in the CRC Handbook on Computational Geometry.","key":"22_CR11"},{"key":"22_CR12","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"},{"doi-asserted-by":"crossref","unstructured":"M. Pocchiola and G. Vegter. Pseudotriangulations: Theory and applications. In Proceedings of the Twelfth Annual Symposium on Computational Geometry, pages 291\u2013300. ACM, 24\u201326 May 1996.","key":"22_CR13","DOI":"10.1145\/237218.237398"},{"issue":"3","key":"22_CR14","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1142\/S0218195996000204","volume":"6","author":"M. Pocchiola","year":"1996","unstructured":"M. Pocchiola and G. Vegter. The visibility complex. Internatational Journal of Computational Geometry & Applications, 6(3):279\u2013308, 1996.","journal-title":"Internatational Journal of Computational Geometry & Applications"},{"key":"22_CR15","series-title":"Technical Report CS-91-02","volume-title":"Fully dynamic techniques for reachability in planar sT-graphs","author":"S. Sairam","year":"1990","unstructured":"S. Sairam, R. F. Cohen, R. Tamassia, and J. S. Vitter. Fully dynamic techniques for reachability in planar sT-graphs. Technical Report CS-91-02, Department of Computer Science, Brown University, Providence, Rhode Island, 02912-1910, Dec. 1990."},{"key":"22_CR16","first-page":"335","volume-title":"Computational Geometry, volume 2 of Machine Intelligence and Pattern Recognition","author":"G. T. Toussaint","year":"1985","unstructured":"G. T. Toussaint. Movable separability of sets. In G. T. Toussaint, editor, Computational Geometry, volume 2 of Machine Intelligence and Pattern Recognition, pages 335\u2013375. Elsevier, Amsterdam, 1985."},{"issue":"4","key":"22_CR17","doi-asserted-by":"crossref","first-page":"728","DOI":"10.1137\/0216049","volume":"16","author":"P. Widmayer","year":"1987","unstructured":"P. Widmayer, Y. F. Wu, and C. K. Wong. On some distance problems in fixed orientations. SIAM J. Comput., 16(4):728\u2013746, Aug. 1987.","journal-title":"SIAM J. Comput."},{"issue":"3","key":"22_CR18","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1137\/S0097539792229672","volume":"24","author":"C.-D. Yang","year":"1995","unstructured":"C.-D. Yang, D. T. Lee, and C. K. Wong. Rectilinear path problems among rectilinear obstacles revisited. SIAM J. Comput., 24(3):457\u2013472, June 1995.","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-63307-3_64","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T00:15:43Z","timestamp":1559002543000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63307-3_64"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540633075","9783540694229"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-63307-3_64","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}