{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:29:47Z","timestamp":1760441387579,"version":"3.37.3"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,11,22]],"date-time":"2016-11-22T00:00:00Z","timestamp":1479772800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2016,11,22]],"date-time":"2016-11-22T00:00:00Z","timestamp":1479772800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004083","name":"Ministry of Science ICT and Future Planning","doi-asserted-by":"publisher","award":["013R1A1A1A05006927"],"award-info":[{"award-number":["013R1A1A1A05006927"]}],"id":[{"id":"10.13039\/501100004083","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002701","name":"Ministry of Education","doi-asserted-by":"publisher","award":["2015R1D1A1A01057220"],"award-info":[{"award-number":["2015R1D1A1A01057220"]}],"id":[{"id":"10.13039\/501100002701","id-type":"DOI","asserted-by":"publisher"}]},{"name":"The ELC project","award":["24106008"],"award-info":[{"award-number":["24106008"]}]},{"name":"US-Israel Binational Science Foundation","award":["2010074"],"award-info":[{"award-number":["2010074"]}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1018388","CCF-1526406"],"award-info":[{"award-number":["CCF-1018388","CCF-1526406"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Grant-in-Aid for Scientific Research","award":["24106005","24700008"],"award-info":[{"award-number":["24106005","24700008"]}]},{"name":"Grant-in-Aid for Scientific Research","award":["24220003","15K00009"],"award-info":[{"award-number":["24220003","15K00009"]}]},{"DOI":"10.13039\/501100001858","name":"VINNOVA","doi-asserted-by":"publisher","award":["2014-03476"],"award-info":[{"award-number":["2014-03476"]}],"id":[{"id":"10.13039\/501100001858","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"}]},{"name":"Swedish Transport Administration Trafikverket","award":["UTM-OK"],"award-info":[{"award-number":["UTM-OK"]}]},{"name":"JSPS\/MEXT Grant-in-Aid for Scientific Research","award":["12H00855 and 15H02665"],"award-info":[{"award-number":["12H00855 and 15H02665"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2017,4]]},"DOI":"10.1007\/s00454-016-9841-z","type":"journal-article","created":{"date-parts":[[2016,11,22]],"date-time":"2016-11-22T17:34:28Z","timestamp":1479836068000},"page":"674-701","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Computing the $$L_1$$ Geodesic Diameter and Center of a Polygonal Domain"],"prefix":"10.1007","volume":"57","author":[{"given":"Sang Won","family":"Bae","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matias","family":"Korman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joseph S. B.","family":"Mitchell","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yoshio","family":"Okamoto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Valentin","family":"Polishchuk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haitao","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,11,22]]},"reference":[{"key":"9841_CR1","unstructured":"Ahn, H.-K., Barba, L., Bose, P., De Carufel, J.-L., Korman, M., Oh, E.: A linear-time algorithm for the geodesic center of a simple polygon. In: Proceedings of the 31st Symposium on Computational Geometry, pp. 209\u2013223 (2015)"},{"issue":"1\u20134","key":"9841_CR2","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/BF01553882","volume":"4","author":"B Aronov","year":"1989","unstructured":"Aronov, B.: On the geodesic Voronoi diagram of point sites in a simple polygon. Algorithmica 4(1\u20134), 109\u2013140 (1989)","journal-title":"Algorithmica"},{"key":"9841_CR3","unstructured":"Asano, T., Toussaint, G.: Computing the geodesic center of a simple polygon. Technical Report SOCS-85.32, McGill University, Montreal (1985)"},{"key":"9841_CR4","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1007\/s00454-013-9527-8","volume":"50","author":"SW Bae","year":"2013","unstructured":"Bae, S.W., Korman, M., Okamoto, Y.: The geodesic diameter of polygonal domains. Discrete Comput. Geom. 50, 306\u2013329 (2013)","journal-title":"Discrete Comput. Geom."},{"key":"9841_CR5","doi-asserted-by":"publisher","unstructured":"Bae, S.W., Korman, M., Okamoto, Y.: Computing the geodesic centers of a polygonal domain. In: Proceedings of the 26th Canadian Conference on Computational Geometry (2014). Journal version to appear in Computational Geometry: Theory and Applications. doi:\n                    10.1016\/j.comgeo.2015.10.009","DOI":"10.1016\/j.comgeo.2015.10.009"},{"key":"9841_CR6","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1016\/j.comgeo.2015.02.005","volume":"48","author":"SW Bae","year":"2015","unstructured":"Bae, S.W., Korman, M., Okamoto, Y., Wang, H.: Computing the $$L_1$$ geodesic diameter and center of a simple polygon in linear time. Comput. Geom. 48, 495\u2013505 (2015)","journal-title":"Comput. Geom."},{"issue":"4","key":"9841_CR7","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":"9841_CR8","doi-asserted-by":"crossref","unstructured":"Chazelle, B.: A theorem on polygon cutting with applications. In: Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, pp. 339\u2013349 (1982)","DOI":"10.1109\/SFCS.1982.58"},{"key":"9841_CR9","doi-asserted-by":"crossref","unstructured":"Chen, D.Z., Wang, H.: A nearly optimal algorithm for finding $$L_1$$ shortest paths among polygonal obstacles in the plane. In: Proceedings of the 19th European Symposium on Algorithms, pp. 481\u2013492 (2011)","DOI":"10.1007\/978-3-642-23719-5_41"},{"key":"9841_CR10","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). Journal version published online in Algorithmica, 2015"},{"key":"9841_CR11","unstructured":"Chen, D.Z., Wang, H.: $$L_1$$ shortest path queries among polygonal obstacles in the plane. In: Proceedings of the 30th Symposium on Theoretical Aspects of Computer Science, pp. 293\u2013304 (2013)"},{"key":"9841_CR12","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/BF02187733","volume":"4","author":"H Edelsbrunner","year":"1989","unstructured":"Edelsbrunner, H., Guibas, L.J., Sharir, M.: The upper envelope of piecewise linear functions: algorithms and applications. Discrete Comput. Geom. 4, 311\u2013336 (1989)","journal-title":"Discrete Comput. Geom."},{"issue":"1\u20134","key":"9841_CR13","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/BF01840360","volume":"2","author":"LJ Guibas","year":"1987","unstructured":"Guibas, L.J., 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":"9841_CR14","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":"6","key":"9841_CR15","doi-asserted-by":"publisher","first-page":"1612","DOI":"10.1137\/S0097539793253577","volume":"26","author":"J Hershberger","year":"1997","unstructured":"Hershberger, J., Suri, S.: Matrix searching with the shortest-path metric. SIAM J. Comput. 26(6), 1612\u20131634 (1997)","journal-title":"SIAM J. Comput."},{"issue":"9","key":"9841_CR16","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."},{"issue":"4","key":"9841_CR17","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."},{"key":"9841_CR18","unstructured":"Mitchell, J.S.B.: An optimal algorithm for shortest rectilinear paths among obstacles. In: The 1st Canadian Conference on Computational Geometry (1989)"},{"issue":"1","key":"9841_CR19","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":"4","key":"9841_CR20","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(4), 319\u2013352 (1998)","journal-title":"Algorithmica"},{"issue":"1","key":"9841_CR21","doi-asserted-by":"publisher","first-page":"611","DOI":"10.1007\/BF02187751","volume":"4","author":"R Pollack","year":"1989","unstructured":"Pollack, R., Sharir, M., Rote, G.: Computing the geodesic center of a simple polygon. Discrete Comput. Geom. 4(1), 611\u2013626 (1989)","journal-title":"Discrete Comput. Geom."},{"key":"9841_CR22","doi-asserted-by":"crossref","unstructured":"Schuierer, S.: Computing the $$L_1$$-diameter and center of a simple rectilinear polygon. In: Proceedings of the International Conference on Computing and Information, pp. 214\u2013229 (1994)","DOI":"10.1007\/3-540-58218-5_30"},{"key":"9841_CR23","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/0022-0000(89)90045-7","volume":"39","author":"S Suri","year":"1989","unstructured":"Suri, S.: Computing geodesic furthest neighbors in simple polygons. J. Comput. Syst. Sci. 39, 220\u2013235 (1989)","journal-title":"J. Comput. Syst. Sci."},{"key":"9841_CR24","unstructured":"Wang, H.: On the geodesic centers of polygonal domains. In: Proceedings of the 24th European Symposium on Algorithms, pp. 77:1\u201377:17 (2016)"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-016-9841-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-016-9841-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-016-9841-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T06:35:32Z","timestamp":1589697332000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-016-9841-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11,22]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,4]]}},"alternative-id":["9841"],"URL":"https:\/\/doi.org\/10.1007\/s00454-016-9841-z","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2016,11,22]]},"assertion":[{"value":"23 December 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 October 2016","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 November 2016","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 November 2016","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}