{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T16:52:05Z","timestamp":1744217525029,"version":"3.37.3"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2015,8,29]],"date-time":"2015-08-29T00:00:00Z","timestamp":1440806400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2015,8,29]],"date-time":"2015-08-29T00:00:00Z","timestamp":1440806400000},"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-1217906"],"award-info":[{"award-number":["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":[[2017,1]]},"DOI":"10.1007\/s00453-015-0058-y","type":"journal-article","created":{"date-parts":[[2015,8,28]],"date-time":"2015-08-28T15:23:47Z","timestamp":1440775427000},"page":"40-64","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Computing the Visibility Polygon of an Island in a Polygonal Domain"],"prefix":"10.1007","volume":"77","author":[{"given":"Danny Z.","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haitao","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,8,29]]},"reference":[{"issue":"1","key":"58_CR1","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/BF01840436","volume":"1","author":"T Asano","year":"1986","unstructured":"Asano, T., Asano, T., Guibas, L., Hershberger, J., Imai, H.: Visibility of disjoint polygons. Algorithmica 1(1), 49\u201363 (1986)","journal-title":"Algorithmica"},{"issue":"3","key":"58_CR2","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"},{"key":"58_CR3","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1007\/s004539910018","volume":"26","author":"AJ Briggs","year":"2000","unstructured":"Briggs, A.J., Donald, B.R.: Visibility-based planning of sensor control strategies. Algorithmica 26, 364\u2013388 (2000)","journal-title":"Algorithmica"},{"key":"58_CR4","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."},{"key":"58_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."},{"key":"58_CR6","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 (ESA), pp. 481\u2013492 (2011)","DOI":"10.1007\/978-3-642-23719-5_41"},{"key":"58_CR7","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/j.comgeo.2014.08.003","volume":"48","author":"DZ Chen","year":"2015","unstructured":"Chen, D.Z., Wang, H.: Visibility and ray shooting queries in polygonal domains. Comput. Geom. Theory Appl. 48, 31\u201341 (2015)","journal-title":"Comput. Geom. Theory Appl."},{"key":"58_CR8","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1016\/j.comgeo.2015.02.001","volume":"48","author":"DZ Chen","year":"2015","unstructured":"Chen, D.Z., Wang, H.: Weak visibility queries of line segments in simple polygons. Comput. Geom. Theory Appl. 48, 443\u2013452 (2015)","journal-title":"Comput. Geom. Theory Appl."},{"issue":"2","key":"58_CR9","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1016\/0196-6774(81)90019-5","volume":"2","author":"H ElGindy","year":"1981","unstructured":"ElGindy, H., Avis, D.: A linear algorithm for computing the visibility polygon from a point. J. Algorithms 2(2), 186\u2013197 (1981)","journal-title":"J. Algorithms"},{"key":"58_CR10","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/0196-6774(91)90024-S","volume":"12","author":"SK Ghosh","year":"1991","unstructured":"Ghosh, S.K.: Computing the visibility polygon from a convex set and related problems. J. Algorithms 12, 75\u201395 (1991)","journal-title":"J. Algorithms"},{"issue":"5","key":"58_CR11","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":"58_CR12","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":"1","key":"58_CR13","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1137\/S0097539791221505","volume":"24","author":"P Heffernan","year":"1995","unstructured":"Heffernan, P., Mitchell, J.: An optimal algorithm for computing visibility in the plane. SIAM J. Comput. 24(1), 184\u2013201 (1995)","journal-title":"SIAM J. Comput."},{"issue":"9","key":"58_CR14","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. Theory Appl. 42(9), 873\u2013884 (2009)","journal-title":"Comput. Geom. Theory Appl."},{"key":"58_CR15","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1080\/00207169008803824","volume":"32","author":"B Joe","year":"1990","unstructured":"Joe, B.: On the correctness of a linear-time visibility polygon algorithm. Int. J. Comput. Math. 32, 155\u2013172 (1990)","journal-title":"Int. J. Comput. Math."},{"key":"58_CR16","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"},{"issue":"4","key":"58_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."},{"issue":"2","key":"58_CR18","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":"58_CR19","doi-asserted-by":"publisher","first-page":"594","DOI":"10.1016\/0734-189X(86)90044-7","volume":"34","author":"DT Lee","year":"1986","unstructured":"Lee, D.T., Lin, A.K.: Computing the visibility polygon from an edge. Comput. Vis. Graph. Image Process. 34, 594\u2013606 (1986)","journal-title":"Comput. Vis. Graph. Image Process."},{"issue":"2","key":"58_CR20","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":"58_CR21","doi-asserted-by":"crossref","unstructured":"Suri, S., O\u2019Rourke, J.: Worst-case optimal algorithms for constructing visibility polygons with holes. In: Proceedings of the 2nd Annual Symposium on Computational Geometry, pp. 14\u201323 (1986)","DOI":"10.1145\/10515.10517"},{"key":"58_CR22","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/0020-0190(85)90044-4","volume":"20","author":"E Welzl","year":"1985","unstructured":"Welzl, E.: Constructing the visibility graph for $$n$$ line segments in $$O(n^2)$$ time. Inf. Process. Lett. 20, 167\u2013171 (1985)","journal-title":"Inf. Process. Lett."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0058-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-0058-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0058-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0058-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T06:30:54Z","timestamp":1589697054000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-0058-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,8,29]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["58"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-0058-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2015,8,29]]},"assertion":[{"value":"26 November 2014","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 August 2015","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 August 2015","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}