{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T06:21:18Z","timestamp":1725603678440},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642237188"},{"type":"electronic","value":"9783642237195"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-23719-5_41","type":"book-chapter","created":{"date-parts":[[2011,8,30]],"date-time":"2011-08-30T13:14:33Z","timestamp":1314710073000},"page":"481-492","source":"Crossref","is-referenced-by-count":9,"title":["A Nearly Optimal Algorithm for Finding L 1 Shortest Paths among Polygonal Obstacles in the Plane"],"prefix":"10.1007","author":[{"given":"Danny Z.","family":"Chen","sequence":"first","affiliation":[]},{"given":"Haitao","family":"Wang","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"41_CR1","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1142\/S0218195994000252","volume":"4","author":"R. Bar-Yehuda","year":"1994","unstructured":"Bar-Yehuda, R., Chazelle, B.: Triangulating disjoint Jordan chains. International Journal of Computational Geometry and Applications\u00a04(4), 475\u2013481 (1994)","journal-title":"International Journal of Computational Geometry and Applications"},{"key":"41_CR2","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1007\/BF02574703","volume":"6","author":"B. Chazelle","year":"1991","unstructured":"Chazelle, B.: Triangulating a simple polygon in linear time. Discrete and Computational Geometry\u00a06, 485\u2013524 (1991)","journal-title":"Discrete and Computational Geometry"},{"issue":"4","key":"41_CR3","doi-asserted-by":"publisher","first-page":"1223","DOI":"10.1137\/S0097539796307194","volume":"29","author":"D. Chen","year":"2000","unstructured":"Chen, D., Klenk, K., Tu, H.Y.: Shortest path queries among weighted obstacles in the rectilinear plane. SIAM Journal on Computing\u00a029(4), 1223\u20131246 (2000)","journal-title":"SIAM Journal on Computing"},{"key":"41_CR4","unstructured":"Chen, D., Wang, H.: Computing shortest paths among curved obstacles in the plane. In: arXiv:1103.3911 (2011)"},{"key":"41_CR5","doi-asserted-by":"crossref","unstructured":"Clarkson, K.: Approximation algorithms for shortest path motion planning. In: Proc. of the 19th Annual ACM Symposium on Theory of Computing, pp. 56\u201365 (1987)","DOI":"10.1145\/28395.28402"},{"key":"41_CR6","doi-asserted-by":"crossref","unstructured":"Clarkson, K., Kapoor, S., Vaidya, P.: Rectilinear shortest paths through polygonal obstacles in O(n log2 n) time. In: Proc. of the 3rd Annual Symposium on Computational Geometry, pp. 251\u2013257 (1987)","DOI":"10.1145\/41958.41985"},{"key":"41_CR7","doi-asserted-by":"crossref","unstructured":"Clarkson, K., Kapoor, S., Vaidya, P.: Rectilinear shortest paths through polygonal obstacles in O(n log2\/3 n) time (1988) (manuscript)","DOI":"10.1145\/41958.41985"},{"issue":"2","key":"41_CR8","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1137\/0215023","volume":"15","author":"H. Edelsbrunner","year":"1986","unstructured":"Edelsbrunner, H., Guibas, L., Stolfi, J.: Optimal point location in a monotone subdivision. SIAM Journal on Computing\u00a015(2), 317\u2013340 (1986)","journal-title":"SIAM Journal on Computing"},{"issue":"5","key":"41_CR9","doi-asserted-by":"publisher","first-page":"888","DOI":"10.1137\/0220055","volume":"20","author":"S. Ghosh","year":"1991","unstructured":"Ghosh, S., Mount, D.: An output-sensitive algorithm for computing visibility. SIAM Journal on Computing\u00a020(5), 888\u2013910 (1991)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"41_CR10","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/0925-7721(94)90010-8","volume":"4","author":"J. Hershberger","year":"1994","unstructured":"Hershberger, J., Snoeyink, J.: Computing minimum length paths of a given homotopy class. Computational Geometry: Theory and Applications\u00a04(2), 63\u201397 (1994)","journal-title":"Computational Geometry: Theory and Applications"},{"issue":"6","key":"41_CR11","doi-asserted-by":"publisher","first-page":"2215","DOI":"10.1137\/S0097539795289604","volume":"28","author":"J. Hershberger","year":"1999","unstructured":"Hershberger, J., Suri, S.: An optimal algorithm for Euclidean shortest paths in the plane. SIAM Journal on Computing\u00a028(6), 2215\u20132256 (1999)","journal-title":"SIAM Journal on Computing"},{"key":"41_CR12","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1016\/S0019-9958(85)80044-9","volume":"64","author":"S. Hertel","year":"1985","unstructured":"Hertel, S., Mehlhorn, K.: Fast triangulation of the plane with respect to simple polygons. Information and Control\u00a064, 52\u201376 (1985)","journal-title":"Information and Control"},{"issue":"9","key":"41_CR13","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1016\/j.comgeo.2009.02.005","volume":"42","author":"R. Inkulu","year":"2009","unstructured":"Inkulu, R., Kapoor, S.: Planar rectilinear shortest path computation using corridors. Computational Geometry: Theory and Applications\u00a042(9), 873\u2013884 (2009)","journal-title":"Computational Geometry: Theory and Applications"},{"key":"41_CR14","unstructured":"Inkulu, R., Kapoor, S., Maheshwari, S.: A near optimal algorithm for finding Euclidean shortest path in polygonal domain. In: arXiv:1011.6481v1 (2010)"},{"issue":"4","key":"41_CR15","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1007\/PL00009323","volume":"18","author":"S. Kapoor","year":"1997","unstructured":"Kapoor, S., Maheshwari, S., Mitchell, J.: An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane. Discrete and Computational Geometry\u00a018(4), 377\u2013383 (1997)","journal-title":"Discrete and Computational Geometry"},{"issue":"1","key":"41_CR16","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1137\/0212002","volume":"12","author":"D. Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, D.: Optimal search in planar subdivisions. SIAM Journal on Computing\u00a012(1), 28\u201335 (1983)","journal-title":"SIAM Journal on Computing"},{"key":"41_CR17","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1002\/net.3230110307","volume":"11","author":"R. Larsona","year":"1981","unstructured":"Larsona, R., Li, V.: Finding minimum rectilinear distance paths in the presence of barriers. Networks\u00a011, 285\u2013304 (1981)","journal-title":"Networks"},{"key":"41_CR18","unstructured":"Mitchell, J.: An optimal algorithm for shortest rectilinear paths among obstacles. In: Abstracts of the 1st Canadian Conference on Computational Geometry (1989)"},{"issue":"1","key":"41_CR19","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/BF01758836","volume":"8","author":"J. Mitchell","year":"1992","unstructured":"Mitchell, J.: L 1 shortest paths among polygonal obstacles in the plane. Algorithmica\u00a08(1), 55\u201388 (1992)","journal-title":"Algorithmica"},{"issue":"3","key":"41_CR20","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1142\/S0218195996000216","volume":"6","author":"J. Mitchell","year":"1996","unstructured":"Mitchell, J.: Shortest paths among obstacles in the plane. International Journal of Computational Geometry and Applications\u00a06(3), 309\u2013332 (1996)","journal-title":"International Journal of Computational Geometry and Applications"},{"key":"41_CR21","doi-asserted-by":"crossref","unstructured":"de Rezende, P., Lee, D., Wu, Y.: Rectilinear shortest paths with rectangular barriers. In: Proc. of the 1st Annual Symposium on Computational Geometry, pp. 204\u2013213 (1985)","DOI":"10.1145\/323233.323260"},{"issue":"5","key":"41_CR22","doi-asserted-by":"publisher","first-page":"982","DOI":"10.1145\/185675.185795","volume":"41","author":"J. Storer","year":"1994","unstructured":"Storer, J., Reif, J.: Shortest paths in the plane with polygonal obstacles. Journal of the ACM\u00a041(5), 982\u20131012 (1994)","journal-title":"Journal of the ACM"},{"issue":"7","key":"41_CR23","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1007\/BF02067242","volume":"33","author":"P. Widmayer","year":"1991","unstructured":"Widmayer, P.: On graphs preserving rectilinear shortest paths in the presence of obstacles. Annals of Operations Research\u00a033(7), 557\u2013575 (1991)","journal-title":"Annals of Operations Research"},{"issue":"4","key":"41_CR24","doi-asserted-by":"publisher","first-page":"728","DOI":"10.1137\/0216049","volume":"16","author":"P. Widmayer","year":"1987","unstructured":"Widmayer, P., Wu, Y., Wong, C.: On some distance problems in fixed orientations. SIAM Journal on Computing\u00a016(4), 728\u2013746 (1987)","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2011"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-23719-5_41","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,14]],"date-time":"2019-06-14T16:08:49Z","timestamp":1560528529000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-23719-5_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642237188","9783642237195"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-23719-5_41","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}