{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:19:46Z","timestamp":1740122386573,"version":"3.37.3"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,1,27]],"date-time":"2022-01-27T00:00:00Z","timestamp":1643241600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,27]],"date-time":"2022-01-27T00:00:00Z","timestamp":1643241600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001843","name":"Science and Engineering Research Board","doi-asserted-by":"publisher","award":["MTR\/2017\/000474"],"award-info":[{"award-number":["MTR\/2017\/000474"]}],"id":[{"id":"10.13039\/501100001843","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,11]]},"DOI":"10.1007\/s10878-022-00846-1","type":"journal-article","created":{"date-parts":[[2022,1,27]],"date-time":"2022-01-27T17:02:34Z","timestamp":1643302954000},"page":"3056-3082","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Visibility polygons and visibility graphs among dynamic polygonal obstacles in the plane"],"prefix":"10.1007","volume":"44","author":[{"given":"Sanjana","family":"Agrawal","sequence":"first","affiliation":[]},{"given":"R.","family":"Inkulu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,1,27]]},"reference":[{"key":"846_CR1","doi-asserted-by":"crossref","unstructured":"Agrawal S,\u00a0Inkulu R (2020) Visibility polygon queries among dynamic polygonal obstacles in plane. In:Proceedings of International Computing and Combinatorics Conference, pages 136\u2013148","DOI":"10.1007\/978-3-030-58150-3_11"},{"key":"846_CR2","unstructured":"Akbari K,\u00a0Ghodsi M (2010) Visibility maintenance of a moving segment observer inside polygons with holes. In:Proceedings of Canadian Conference on Computational Geometry, pages 117\u2013120"},{"issue":"4","key":"846_CR3","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/s00454-001-0089-9","volume":"27","author":"B Aronov","year":"2002","unstructured":"Aronov B, Guibas LJ, Teichmann M, Zhang L (2002) Visibility queries and maintenance in simple polygons. Discret Comput Geom 27(4):461\u2013483","journal-title":"Discret Comput Geom"},{"issue":"1","key":"846_CR4","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/BF01840436","volume":"1","author":"T Asano","year":"1986","unstructured":"Asano T, Asano T, Guibas LJ, Hershberger J, Imai H (1986) Visibility of disjoint polygons. Algorithmica 1(1):49\u201363","journal-title":"Algorithmica"},{"issue":"4","key":"846_CR5","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 (1994) Triangulating disjoint jordan chains. Int J Comput Geom Appl 4(4):475\u2013481","journal-title":"Int J Comput Geom Appl"},{"key":"846_CR6","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1016\/j.comgeo.2012.10.004","volume":"46","author":"MN Baygi","year":"2013","unstructured":"Baygi MN, Ghodsi M (2013) Space\/query-time tradeoff for computing the visibility polygon. Comput Geom 46:371\u2013381","journal-title":"Comput Geom"},{"issue":"3","key":"846_CR7","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/S0925-7721(01)00070-0","volume":"23","author":"P Bose","year":"2002","unstructured":"Bose P, Lubiw A, Munro JI (2002) Efficient visibility queries in simple polygons. Comput Geom 23(3):313\u2013335","journal-title":"Comput Geom"},{"key":"846_CR8","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1007\/BF02574703","volume":"6","author":"B Chazelle","year":"1991","unstructured":"Chazelle B (1991) Triangulating a simple polygon in linear time. Discret Comput Geom 6:485\u2013524","journal-title":"Discret Comput Geom"},{"issue":"5","key":"846_CR9","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/S0020-0190(97)00211-1","volume":"65","author":"DZ Chen","year":"1998","unstructured":"Chen DZ, Daescu O (1998) Maintaining visibility of a polygon with a moving point of view. Inform Process Lett 65(5):269\u2013275","journal-title":"Inform Process Lett"},{"issue":"1","key":"846_CR10","first-page":"473","volume":"7","author":"DZ Chen","year":"2016","unstructured":"Chen DZ, Inkulu R, Wang H (2016) Two-point $$L_1$$ shortest path queries in the plane. J Comput Geom 7(1):473\u2013519","journal-title":"J Comput Geom"},{"issue":"1","key":"846_CR11","first-page":"316","volume":"6","author":"DZ Chen","year":"2015","unstructured":"Chen DZ, Wang H (2015) A new algorithm for computing visibility graphs of polygonal obstacles in the plane. J Comput Geom 6(1):316\u2013345","journal-title":"J Comput Geom"},{"issue":"2","key":"846_CR12","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/j.comgeo.2014.08.003","volume":"48","author":"DZ Chen","year":"2015","unstructured":"Chen DZ, Wang H (2015) Visibility and ray shooting queries in polygonal domains. Comput Geom 48(2):31\u201341","journal-title":"Comput Geom"},{"key":"846_CR13","doi-asserted-by":"crossref","unstructured":"Choudhury T,\u00a0Inkulu R (2019) Maintaining the visibility graph of a dynamic simple polygon. In:Proceedings of Conference on Algorithms and Discrete Applied Mathematics, pages 42\u201352","DOI":"10.1007\/978-3-030-11509-8_4"},{"key":"846_CR14","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to Algorithms. The MIT Press, USA"},{"issue":"1","key":"846_CR15","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0146-664X(79)90076-5","volume":"11","author":"LS Davis","year":"1979","unstructured":"Davis LS, Benedikt ML (1979) Computational models of space: isovists and isovist fields. Comput Gr Image Process 11(1):49\u201372","journal-title":"Comput Gr Image Process"},{"issue":"2","key":"846_CR16","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1016\/0196-6774(81)90019-5","volume":"2","author":"HA ElGindy","year":"1981","unstructured":"ElGindy HA, Avis D (1981) A linear algorithm for computing the visibility polygon from a point. J Algorithms 2(2):186\u2013197","journal-title":"J Algorithms"},{"issue":"1","key":"846_CR17","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/0196-6774(91)90024-S","volume":"12","author":"SK Ghosh","year":"1991","unstructured":"Ghosh SK (1991) Computing the visibility polygon from a convex set and related problems. J Algorithms 12(1):75\u201395","journal-title":"J Algorithms"},{"key":"846_CR18","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511543340","volume-title":"Visibility algorithms in the plane","author":"SK Ghosh","year":"2007","unstructured":"Ghosh SK (2007) Visibility algorithms in the plane. Cambridge University Press, New York"},{"issue":"5","key":"846_CR19","doi-asserted-by":"publisher","first-page":"888","DOI":"10.1137\/0220055","volume":"20","author":"SK Ghosh","year":"1991","unstructured":"Ghosh SK, Mount DM (1991) An output-sensitive algorithm for computing visibility graphs. SIAM J Comput 20(5):888\u2013910","journal-title":"SIAM J Comput"},{"issue":"1","key":"846_CR20","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1006\/jagm.1995.0797","volume":"23","author":"MT Goodrich","year":"1997","unstructured":"Goodrich MT, Tamassia R (1997) Dynamic ray shooting and shortest paths in planar subdivisions via balanced geodesic triangulations. J Algorithms 23(1):51\u201373","journal-title":"J Algorithms"},{"issue":"1","key":"846_CR21","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1137\/S0097539791221505","volume":"24","author":"PJ Heffernan","year":"1995","unstructured":"Heffernan PJ, Mitchell JSB (1995) An optimal algorithm for computing visibility in the plane. SIAM J Comput 24(1):184\u2013201","journal-title":"SIAM J Comput"},{"key":"846_CR22","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/BF01553883","volume":"4","author":"J Hershberger","year":"1989","unstructured":"Hershberger J (1989) An optimal visibility graph algorithm for triangulated simple polygons. Algorithmica 4:141\u2013155","journal-title":"Algorithmica"},{"issue":"9","key":"846_CR23","doi-asserted-by":"publisher","first-page":"852","DOI":"10.1016\/j.comgeo.2009.02.004","volume":"42","author":"R Inkulu","year":"2009","unstructured":"Inkulu R, Kapoor S (2009) Visibility queries in a polygonal region. Comput Geom 42(9):852\u2013864","journal-title":"Comput Geom"},{"key":"846_CR24","doi-asserted-by":"crossref","unstructured":"Inkulu R,\u00a0Nitish T (2017) Incremental algorithms to update visibility polygons. In:Proceedings of Conference on Algorithms and Discrete Applied Mathematics, pages 205\u2013218","DOI":"10.1007\/978-3-319-53007-9_19"},{"issue":"1","key":"846_CR25","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1142\/S021819592050003X","volume":"30","author":"R Inkulu","year":"2020","unstructured":"Inkulu R, Sowmya K, Thakur NP (2020) Dynamic algorithms for visibility polygons in simple polygons. Int J Comput Geom Appl 30(1):51\u201378","journal-title":"Int J Comput Geom Appl"},{"issue":"4","key":"846_CR26","doi-asserted-by":"publisher","first-page":"458","DOI":"10.1007\/BF01937271","volume":"27","author":"B Joe","year":"1987","unstructured":"Joe B, Simpson R (1987) Corrections to Lee\u2019s visibility polygon algorithm. BIT Numer Math 27(4):458\u2013473","journal-title":"BIT Numer Math"},{"key":"846_CR27","doi-asserted-by":"crossref","unstructured":"Kapoor S (1999) Efficient computation of geodesic shortest paths. In:Proceedings of Symposium on Theory of Computing, pages 770\u2013779","DOI":"10.1145\/301250.301449"},{"key":"846_CR28","doi-asserted-by":"crossref","unstructured":"Kapoor S, Maheshwari S\u00a0N (1988) Efficient algorithms for Euclidean shortest path and visibility problems with polygonal obstacles. In:Proceedings of Symposium on Computational Geometry, pages 172\u2013182","DOI":"10.1145\/73393.73411"},{"issue":"3","key":"846_CR29","doi-asserted-by":"publisher","first-page":"847","DOI":"10.1137\/S0097539795253591","volume":"30","author":"S Kapoor","year":"2000","unstructured":"Kapoor S, Maheshwari SN (2000) Efficiently constructing the visibility graph of a simple polygon with obstacles. SIAM J Comput 30(3):847\u2013871","journal-title":"SIAM J Comput"},{"issue":"4","key":"846_CR30","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1007\/PL00009323","volume":"18","author":"S Kapoor","year":"1997","unstructured":"Kapoor S, Maheshwari SN, Mitchell JSB (1997) An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane. Discrete Comput Geom 18(4):377\u2013383","journal-title":"Discrete Comput Geom"},{"key":"846_CR31","unstructured":"Lee DT (1978) Proximity and reachability in the Plane. PhD thesis, University of Illinois at Urbana-Champaign, Ph.D. thesis and Technical Report ACT-12"},{"issue":"2","key":"846_CR32","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/0734-189X(83)90065-8","volume":"22","author":"DT Lee","year":"1983","unstructured":"Lee DT (1983) Visibility of a simple polygon. Comput Vision, Gr, Image Process 22(2):207\u2013221","journal-title":"Comput Vision, Gr, Image Process"},{"issue":"7","key":"846_CR33","first-page":"4165","volume":"16","author":"L Lu","year":"2011","unstructured":"Lu L, Yang C, Wang J (2011) Point visibility computing in polygons with holes. J Inform Comput Sci 16(7):4165\u20134173","journal-title":"J Inform Comput Sci"},{"key":"846_CR34","volume-title":"Art gallery theorems and algorithms","author":"J O\u2019Rourke","year":"1987","unstructured":"O\u2019Rourke J (1987) Art gallery theorems and algorithms. Oxford University Press Inc, New York, USA"},{"issue":"2","key":"846_CR35","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1016\/0022-0000(81)90012-X","volume":"23","author":"MH Overmars","year":"1981","unstructured":"Overmars MH, van Leewen J (1981) Maintenance of configurations in the plane. J Comput Syst Sci 23(2):166\u2013204","journal-title":"J Comput Syst Sci"},{"key":"846_CR36","doi-asserted-by":"crossref","unstructured":"Overmars M\u00a0H,\u00a0Welzl E (1988) New methods for computing visibility graphs. In:Proceedings of the Fourth Annual Symposium on Computational Geometry, pages 164\u2013171","DOI":"10.1145\/73393.73410"},{"issue":"4","key":"846_CR37","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/BF02712876","volume":"16","author":"M Pocchiola","year":"1996","unstructured":"Pocchiola M, Vegter G (1996) Topologically sweeping visibility complexes via pseudotriangulations. Discret Comput Geom 16(4):419\u2013453","journal-title":"Discret Comput Geom"},{"key":"846_CR38","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational geometry: an introduction","author":"FP Preparata","year":"1985","unstructured":"Preparata FP, Shamos MI (1985) Computational geometry: an introduction. Springer-Verlag, New York, USA"},{"issue":"1","key":"846_CR39","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1137\/0215014","volume":"15","author":"M Sharir","year":"1986","unstructured":"Sharir M, Schorr A (1986) On shortest paths in polyhedral spaces. SIAM J Comput 15(1):193\u2013215","journal-title":"SIAM J Comput"},{"key":"846_CR40","doi-asserted-by":"crossref","unstructured":"Suri S,\u00a0O\u2019Rourke J (1986) Worst-case optimal algorithms for constructing visibility polygons with holes. In:Proceedings of the Symposium on Computational Geometry, pages 14\u201323","DOI":"10.1145\/10515.10517"},{"issue":"4","key":"846_CR41","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 (1985) Constructing the visibility graph for $$n$$-line segments in $$O(n^2)$$ time. Inform Process Lett 20(4):167\u2013171","journal-title":"Inform Process Lett"},{"key":"846_CR42","doi-asserted-by":"crossref","unstructured":"Zarei A,\u00a0Ghodsi M (2005) Efficient computation of query point visibility in polygons with holes. In:Proceedings of the Symposium on Computational Geometry, pages 314\u2013320","DOI":"10.1145\/1064092.1064140"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00846-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-022-00846-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00846-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,14]],"date-time":"2022-10-14T20:25:39Z","timestamp":1665779139000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-022-00846-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,27]]},"references-count":42,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["846"],"URL":"https:\/\/doi.org\/10.1007\/s10878-022-00846-1","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2022,1,27]]},"assertion":[{"value":"21 December 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 January 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}