{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T16:53:12Z","timestamp":1744217592605,"version":"3.37.3"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2019,1,8]],"date-time":"2019-01-08T00:00:00Z","timestamp":1546905600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,1,8]],"date-time":"2019-01-08T00:00:00Z","timestamp":1546905600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-0916606","CCF-1217906"],"award-info":[{"award-number":["CCF-0916606","CCF-1217906"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1317143"],"award-info":[{"award-number":["CCF-1317143"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,6]]},"DOI":"10.1007\/s00453-018-00540-x","type":"journal-article","created":{"date-parts":[[2019,1,9]],"date-time":"2019-01-09T02:20:30Z","timestamp":1547000430000},"page":"2430-2483","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Computing $$L_1$$ Shortest Paths Among Polygonal Obstacles in the Plane"],"prefix":"10.1007","volume":"81","author":[{"given":"Danny Z.","family":"Chen","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8134-7409","authenticated-orcid":false,"given":"Haitao","family":"Wang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,1,8]]},"reference":[{"issue":"3","key":"540_CR1","doi-asserted-by":"publisher","first-page":"516","DOI":"10.1145\/116825.116827","volume":"38","author":"MJ Atallah","year":"1991","unstructured":"Atallah, M.J., Chen, D.Z., Wagener, H.: An optimal parallel algorithm for the visibility of a simple polygon from a point. J. ACM 38(3), 516\u2013533 (1991)","journal-title":"J. ACM"},{"issue":"4","key":"540_CR2","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. Int. J. Comput. Geom. Appl. 4(4), 475\u2013481 (1994)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"540_CR3","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 Comput. Geom. 6, 485\u2013524 (1991)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"540_CR4","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1007\/BF01377183","volume":"12","author":"B Chazelle","year":"1994","unstructured":"Chazelle, B., Edelsbrunner, H., Grigni, M., Gribas, L., Hershberger, J., Sharir, M., Snoeyink, J.: Ray shooting in polygons using geodesic triangulations. Algorithmica 12(1), 54\u201368 (1994)","journal-title":"Algorithmica"},{"key":"540_CR5","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1007\/BF02187747","volume":"4","author":"B Chazelle","year":"1989","unstructured":"Chazelle, B., Guibas, L.: Visibility and intersection problems in plane geometry. Discrete Comput. Geom. 4, 551\u2013589 (1989)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"540_CR6","doi-asserted-by":"publisher","first-page":"1158","DOI":"10.1137\/110840030","volume":"42","author":"DZ Chen","year":"2013","unstructured":"Chen, D.Z., Hershberger, J., Wang, H.: Computing shortest paths amid convex pseudodisks. SIAM J. Comput. 42(3), 1158\u20131184 (2013)","journal-title":"SIAM J. Comput."},{"key":"540_CR7","first-page":"473","volume":"1","author":"DZ Chen","year":"2016","unstructured":"Chen, D.Z., Inkulu, R., Wang, H.: Two-point $$L_1$$ shortest path queries in the plane. J. Comput. Geom. 1, 473\u2013519 (2016)","journal-title":"J. Comput. Geom."},{"issue":"4","key":"540_CR8","doi-asserted-by":"publisher","first-page":"1223","DOI":"10.1137\/S0097539796307194","volume":"29","author":"DZ Chen","year":"2000","unstructured":"Chen, D.Z., Klenk, K.S., Tu, H.-Y.T.: Shortest path queries among weighted obstacles in the rectilinear plane. SIAM J. Comput. 29(4), 1223\u20131246 (2000)","journal-title":"SIAM J. Comput."},{"key":"540_CR9","doi-asserted-by":"crossref","unstructured":"Chen, D.Z., Wang, H.: Computing the visibility polygon of an island in a polygonal domain. In: Proceedings of the 39th International Colloquium on Automata, Languages and Programming, pp. 218\u2013229 (2012)","DOI":"10.1007\/978-3-642-31594-7_19"},{"key":"540_CR10","doi-asserted-by":"crossref","unstructured":"Chen, D.Z., Wang, H.: Computing shortest paths among curved obstacles in the plane. ACM Trans. Algorithms, 11, Article No. 26 (2015)","DOI":"10.1145\/2660771"},{"key":"540_CR11","doi-asserted-by":"crossref","unstructured":"Clarkson, K., Kapoor, S., Vaidya, P.: Rectilinear shortest paths through polygonal obstacles in $$O(n \\log ^2 n)$$ time. In: Proceedings of the 3rd Annual Symposium on Computational Geometry, pp. 251\u2013257 (1987)","DOI":"10.1145\/41958.41985"},{"key":"540_CR12","doi-asserted-by":"crossref","unstructured":"Clarkson, K., Kapoor, S., Vaidya, P.: Rectilinear shortest paths through polygonal obstacles in $$O(n \\log ^{2\/3} n)$$ time. Manuscript (1988)","DOI":"10.1145\/41958.41985"},{"key":"540_CR13","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/BF02187714","volume":"4","author":"PJ de Rezende","year":"1989","unstructured":"de Rezende, P.J., Lee, D.T., Wu, Y.F.: Rectilinear shortest paths in the presence of rectangular barriers. Discrete Comput. Geom. 4, 41\u201353 (1989)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"540_CR14","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 J. Comput. 15(2), 317\u2013340 (1986)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"540_CR15","doi-asserted-by":"publisher","first-page":"888","DOI":"10.1137\/0220055","volume":"20","author":"SK Ghosh","year":"1991","unstructured":"Ghosh, S.K., Mount, D.M.: An output-sensitive algorithm for computing visibility graphs. SIAM J. Comput. 20(5), 888\u2013910 (1991)","journal-title":"SIAM J. Comput."},{"issue":"1\u20134","key":"540_CR16","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/BF01840360","volume":"2","author":"L Guibas","year":"1987","unstructured":"Guibas, L., Hershberger, J., Leven, D., Sharir, M., Tarjan, R.E.: Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica 2(1\u20134), 209\u2013233 (1987)","journal-title":"Algorithmica"},{"issue":"2","key":"540_CR17","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. Comput. Geom. 4(2), 63\u201397 (1994)","journal-title":"Comput. Geom."},{"issue":"3","key":"540_CR18","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1006\/jagm.1995.1017","volume":"18","author":"J Hershberger","year":"1995","unstructured":"Hershberger, J., Suri, S.: A pedestrian approach to ray shooting: shoot a ray, take a walk. J. Algorithms 18(3), 403\u2013431 (1995)","journal-title":"J. Algorithms"},{"issue":"6","key":"540_CR19","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 J. Comput. 28(6), 2215\u20132256 (1999)","journal-title":"SIAM J. Comput."},{"key":"540_CR20","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. Inf. Control 64, 52\u201376 (1985)","journal-title":"Inf. Control"},{"issue":"9","key":"540_CR21","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. Comput. Geom. 42(9), 873\u2013884 (2009)","journal-title":"Comput. Geom."},{"key":"540_CR22","unstructured":"Inkulu, R., Kapoor, S., Maheshwari, S.N.: A near optimal algorithm for finding Euclidean shortest path in polygonal domain. \n                    arXiv:1011.6481v1\n                    \n                   (2010)"},{"key":"540_CR23","doi-asserted-by":"publisher","first-page":"458","DOI":"10.1007\/BF01937271","volume":"27","author":"B Joe","year":"1987","unstructured":"Joe, B., Simpson, R.B.: Corrections to Lee\u2019s visibility polygon algorithm. BIT 27, 458\u2013473 (1987)","journal-title":"BIT"},{"key":"540_CR24","doi-asserted-by":"crossref","unstructured":"Kapoor, S., Maheshwari, S.N.: Efficient algorithms for Euclidean shortest path and visibility problems with polygonal obstacles. In: Proceedings of the 4th Annual ACM Symposium on Computational Geometry, pp. 172\u2013182 (1988)","DOI":"10.1145\/73393.73411"},{"issue":"4","key":"540_CR25","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1007\/PL00009323","volume":"18","author":"S Kapoor","year":"1997","unstructured":"Kapoor, S., Maheshwari, S.N., Mitchell, J.S.B.: An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane. Discrete Comput. Geom. 18(4), 377\u2013383 (1997)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"540_CR26","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 J. Comput. 12(1), 28\u201335 (1983)","journal-title":"SIAM J. Comput."},{"key":"540_CR27","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1002\/net.3230110307","volume":"11","author":"RC Larson","year":"1981","unstructured":"Larson, R.C., Li, V.O.K.: Finding minimum rectilinear distance paths in the presence of barriers. Networks 11, 285\u2013304 (1981)","journal-title":"Networks"},{"issue":"2","key":"540_CR28","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/0734-189X(83)90065-8","volume":"22","author":"DT Lee","year":"1983","unstructured":"Lee, D.T.: Visibility of a simple polygon. Comput. Vis. Graph. Image Process. 22(2), 207\u2013221 (1983)","journal-title":"Comput. Vis. Graph. Image Process."},{"key":"540_CR29","unstructured":"Mitchell, J.S.B.: An optimal algorithm for shortest rectilinear paths among obstacles. In: Abstracts of the 1st Canadian Conference on Computational Geometry (1989)"},{"issue":"1","key":"540_CR30","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/BF01758836","volume":"8","author":"JSB Mitchell","year":"1992","unstructured":"Mitchell, J.S.B.: $$L_1$$ shortest paths among polygonal obstacles in the plane. Algorithmica 8(1), 55\u201388 (1992)","journal-title":"Algorithmica"},{"issue":"3","key":"540_CR31","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1142\/S0218195996000216","volume":"6","author":"JSB Mitchell","year":"1996","unstructured":"Mitchell, J.S.B.: Shortest paths among obstacles in the plane. Int. J. Comput. Geom. Appl. 6(3), 309\u2013332 (1996)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"540_CR32","unstructured":"Oh, E., Ahn, H.-K.: Voronoi diagrams for a moderate-sized point-set in a simple polygon. In: Proceedings of the 33rd International Symposium on Computational Geometry, pp. 52:1\u201352:15 (2017)"},{"key":"540_CR33","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/PL00009199","volume":"20","author":"E Papadopoulou","year":"1998","unstructured":"Papadopoulou, E., Lee, D.T.: A new approach for the geodesic Voronoi diagram of points in a simple polygon and other restricted polygonal domains. Algorithmica 20, 319\u2013352 (1998)","journal-title":"Algorithmica"},{"issue":"2","key":"540_CR34","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/0020-0190(86)90045-1","volume":"23","author":"H Rohnert","year":"1986","unstructured":"Rohnert, H.: Shortest paths in the plane with convex polygonal obstacles. Inf. Process. Lett. 23(2), 71\u201376 (1986)","journal-title":"Inf. Process. Lett."},{"key":"540_CR35","doi-asserted-by":"crossref","unstructured":"Shamos, M.I., Hoey, D.: Closest-point problems. In: Proceedings of the 16th Annual Symposium on Foundations of Computer Science, pp. 151\u2013162 (1975)","DOI":"10.1109\/SFCS.1975.8"},{"issue":"5","key":"540_CR36","doi-asserted-by":"publisher","first-page":"982","DOI":"10.1145\/185675.185795","volume":"41","author":"JA Storer","year":"1994","unstructured":"Storer, J.A., Reif, J.H.: Shortest paths in the plane with polygonal obstacles. J. ACM 41(5), 982\u20131012 (1994)","journal-title":"J. ACM"},{"issue":"7","key":"540_CR37","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. Ann. Oper. Res. 33(7), 557\u2013575 (1991)","journal-title":"Ann. Oper. Res."},{"issue":"4","key":"540_CR38","doi-asserted-by":"publisher","first-page":"728","DOI":"10.1137\/0216049","volume":"16","author":"P Widmayer","year":"1987","unstructured":"Widmayer, P., Wu, Y.F., Wong, C.K.: On some distance problems in fixed orientations. SIAM J. Comput. 16(4), 728\u2013746 (1987)","journal-title":"SIAM J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-00540-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-00540-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-00540-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T06:33:49Z","timestamp":1589697229000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-00540-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1,8]]},"references-count":38,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2019,6]]}},"alternative-id":["540"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-00540-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2019,1,8]]},"assertion":[{"value":"25 November 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 December 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 January 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}