{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:46:44Z","timestamp":1740109604716,"version":"3.37.3"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,12,5]],"date-time":"2023-12-05T00:00:00Z","timestamp":1701734400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,12,5]],"date-time":"2023-12-05T00:00:00Z","timestamp":1701734400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","award":["715744","819416"],"award-info":[{"award-number":["715744","819416"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Swarnajayanti Fellowship","award":["DST\/SJF\/MSA01\/2017- 18"],"award-info":[{"award-number":["DST\/SJF\/MSA01\/2017- 18"]}]},{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2018302","2018302"],"award-info":[{"award-number":["2018302","2018302"]}],"id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["1176\/18"],"award-info":[{"award-number":["1176\/18"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2024,3]]},"DOI":"10.1007\/s00454-023-00569-y","type":"journal-article","created":{"date-parts":[[2023,12,5]],"date-time":"2023-12-05T20:01:46Z","timestamp":1701806506000},"page":"358-398","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The Parameterized Complexity of Guarding Almost Convex Polygons"],"prefix":"10.1007","volume":"71","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0656-7572","authenticated-orcid":false,"given":"Akanksha","family":"Agrawal","sequence":"first","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]},{"given":"Kristine V. K.","family":"Knudsen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]},{"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,12,5]]},"reference":[{"key":"569_CR1","unstructured":"Abrahamsen, M., Adamaszek, A., Miltzow, T.: Irrational guards are sometimes needed. In: 33rd International Symposium on Computational Geometry (Brisbane 2017). Leibniz Int. Proc. Inform., vol. 77, $$\\#\\,3$$. Leibniz-Zent. Inform., Wadern (2017)"},{"key":"569_CR2","doi-asserted-by":"crossref","unstructured":"Abrahamsen, M., Adamaszek, A., Miltzow, T.: The art gallery problem is $$\\exists {\\mathbb{R}}$$-complete. In: 50th Annual ACM SIGACT Symposium on Theory of Computing (Los Angeles 2018), pp. 65\u201373. ACM, New York (2018)","DOI":"10.1145\/3188745.3188868"},{"key":"569_CR3","unstructured":"Aggarwal, A.: The Art Gallery Theorem: Its Variations, Applications and Algorithmic Aspects. PhD thesis, Johns Hopkins University (1986)"},{"issue":"3","key":"569_CR4","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0020-0190(79)90002-4","volume":"8","author":"B Aspvall","year":"1979","unstructured":"Aspvall, B., Plass, M.F., Tarjan, R.E.: A linear-time algorithm for testing the truth of certain quantified Boolean formulas. Inform. Process. Lett. 8(3), 121\u2013123 (1979)","journal-title":"Inform. Process. Lett."},{"issue":"6","key":"569_CR5","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1016\/0031-3203(81)90002-9","volume":"13","author":"D Avis","year":"1981","unstructured":"Avis, D., Toussaint, G.T.: An efficient algorithm for decomposing a polygon into star-shaped polygons. Pattern Recognit. 13(6), 395\u2013398 (1981)","journal-title":"Pattern Recognit."},{"issue":"6","key":"569_CR6","doi-asserted-by":"publisher","first-page":"1002","DOI":"10.1145\/235809.235813","volume":"43","author":"S Basu","year":"1996","unstructured":"Basu, S., Pollack, R., Roy, M.-F.: On the combinatorial and algebraic complexity of quantifier elimination. J. ACM 43(6), 1002\u20131045 (1996)","journal-title":"J. ACM"},{"key":"569_CR7","unstructured":"Bhattacharya, P., Ghosh, S.K., Pal, S.P.: Constant approximation algorithms for guarding simple polygons using vertex guards (2017). arXiv:1712.05492"},{"key":"569_CR8","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/j.dam.2016.12.015","volume":"228","author":"P Bhattacharya","year":"2017","unstructured":"Bhattacharya, P., Ghosh, S.K., Roy, B.: Approximability of guarding weak visibility polygons. Discrete Appl. Math. 228, 109\u2013129 (2017)","journal-title":"Discrete Appl. Math."},{"key":"569_CR9","unstructured":"Bonnet, \u00c9., Miltzow, T.: Parameterized hardness of art gallery problems. In: 24th Annual European Symposium on Algorithms (Aarhus 2016). Leibniz Int. Proc. Inform., vol. 57, #\u00a019. Leibniz-Zent. Inform., Wadern (2016)"},{"key":"569_CR10","unstructured":"Bonnet, \u00c9., Miltzow, T.: An approximation algorithm for the art gallery problem. In: 33rd International Symposium on Computational Geometry (Brisbane 2017). Leibniz Int. Proc. Inform., vol. 77, #\u00a020. Leibniz-Zent. Inform., Wadern (2017)"},{"key":"569_CR11","doi-asserted-by":"crossref","unstructured":"Bonnet, \u00c9., Miltzow, T.: Parameterized hardness of art gallery problems. ACM Trans. Algorithms 16(4), $$\\#\\,42$$ (2020)","DOI":"10.1145\/3398684"},{"key":"569_CR12","doi-asserted-by":"crossref","unstructured":"Borrmann, D., de\u00a0Rezende, P.J., de\u00a0Souza, C.C., Fekete, S.P., Friedrichs, S., Kr\u00f6ller, A., N\u00fcchter,\u00a0A., Schmidt,\u00a0C., Tozoni, D.C.: Point guards and point clouds: solving general art gallery problems. In: 29th Symposuim on Computational Geometry (Rio de Janeiro 2013), pp. 347\u2013348. ACM, New York (2013)","DOI":"10.1145\/2462356.2462361"},{"issue":"4","key":"569_CR13","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/BF02570718","volume":"14","author":"H Br\u00f6nnimann","year":"1995","unstructured":"Br\u00f6nnimann, H., Goodrich, M.T.: Almost optimal set covers in finite VC-dimension. Discrete Comput. Geom. 14(4), 463\u2013479 (1995)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"569_CR14","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0095-8956(75)90061-1","volume":"18","author":"VA Chv\u00e1tal","year":"1975","unstructured":"Chv\u00e1tal, V.A.: A combinatorial theorem in plane geometry. J. Comb. Theory Ser. B 18(1), 39\u201341 (1975)","journal-title":"J. Comb. Theory Ser. B"},{"key":"569_CR15","doi-asserted-by":"crossref","unstructured":"Clarkson, K.L.: Algorithms for polytope covering and approximation. In: Algorithms and Data Structures (Montr\u00e9al 1993). Lecture Notes in Computer Science, vol. 709, pp. 246\u2013252. Springer, Berlin (1993)","DOI":"10.1007\/3-540-57155-8_252"},{"issue":"4","key":"569_CR16","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1111\/j.1475-3995.2011.00804.x","volume":"18","author":"MC Couto","year":"2011","unstructured":"Couto, M.C., de Rezende, P.J., de Souza, C.C.: An exact algorithm for minimizing vertex guards on art galleries. Int. Trans. Oper. Res. 18(4), 425\u2013448 (2011)","journal-title":"Int. Trans. Oper. Res."},{"key":"569_CR17","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F.V., Kowalik, \u0141., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Cham (2015)","DOI":"10.1007\/978-3-319-21275-3"},{"key":"569_CR18","doi-asserted-by":"crossref","unstructured":"Deshpande, A., Kim, T., Demaine, E.D., Sarma, S.E.: A pseudopolynomial time $$O(\\log n)$$-approximation algorithm for art gallery problems. In: Algorithms and Data Structures (Halifax 2007). Lecture Notes in Computer Science, vol. 4619, pp. 163\u2013174. Springer, Berlin (2007)","DOI":"10.1007\/978-3-540-73951-7_15"},{"key":"569_CR19","volume-title":"Graph Theory","author":"R Diestel","year":"2012","unstructured":"Diestel, R.: Graph Theory. Springer, Heidelberg (2012)"},{"key":"569_CR20","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, London (2013)","DOI":"10.1007\/978-1-4471-5559-1"},{"issue":"6","key":"569_CR21","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1016\/j.ipl.2006.05.014","volume":"100","author":"A Efrat","year":"2006","unstructured":"Efrat, A., Har-Peled, S.: Guarding galleries and terrains. Inform. Process. Lett. 100(6), 238\u2013245 (2006)","journal-title":"Inform. Process. Lett."},{"key":"569_CR22","unstructured":"Eidenbenz, S., Stamm, C., Widmayer, P.: Inapproximability of some art gallery problems. In: 10th Canadian Conference on Computational Geometry (Montr\u00e9al 1998), $$\\#\\,23$$. https:\/\/cccg.ca\/proceedings\/1998\/"},{"issue":"1","key":"569_CR23","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/s00453-001-0040-8","volume":"31","author":"S Eidenbenz","year":"2001","unstructured":"Eidenbenz, S., Stamm, C., Widmayer, P.: Inapproximability results for guarding polygons and terrains. Algorithmica 31(1), 79\u2013113 (2001)","journal-title":"Algorithmica"},{"issue":"3","key":"569_CR24","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1016\/0095-8956(78)90059-X","volume":"24","author":"S Fisk","year":"1978","unstructured":"Fisk, S.: A short proof of Chv\u00e1tal\u2019s watchman theorem. J. Comb. Theory Ser. B 24(3), 374 (1978)","journal-title":"J. Comb. Theory Ser. B"},{"key":"569_CR25","unstructured":"Ghosh, S.K.: Approximation algorithms for art gallery problems. In: Canadian Information Processing Society Congress (Winnipeg 1987), pp. 429\u2013434. CIPS, Toronto (1987)"},{"issue":"6","key":"569_CR26","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1016\/j.dam.2009.12.004","volume":"158","author":"SK Ghosh","year":"2010","unstructured":"Ghosh, S.K.: Approximation algorithms for art gallery problems in polygons. Discrete Appl. Math. 158(6), 718\u2013722 (2010)","journal-title":"Discrete Appl. Math."},{"key":"569_CR27","doi-asserted-by":"crossref","unstructured":"Ghosh, S.K., Goswami, P.P.: Unsolved problems in visibility graphs of points, segments, and polygons. ACM Comput. Surveys 46(2), $$\\#\\,22$$ (2013)","DOI":"10.1145\/2543581.2543589"},{"key":"569_CR28","unstructured":"Giannopoulos, P.: Open problems: guarding problems. In: Lorentz Workshop on Fixed-Parameter Computational Geometry (Leiden 2016)"},{"issue":"1","key":"569_CR29","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/j.comgeo.2013.08.012","volume":"47","author":"A Gilbers","year":"2014","unstructured":"Gilbers, A., Klein, R.: A new upper bound for the VC-dimension of visibility regions. Comput. Geom. 47(1), 61\u201374 (2014)","journal-title":"Comput. Geom."},{"key":"569_CR30","doi-asserted-by":"crossref","unstructured":"Golovach, P.A., Lokshtanov, D., Saurabh, S., Zehavi, M.: Cliquewidth III: the odd case of graph coloring parameterized by cliquewidth. In: 28th Annual ACM-SIAM Symposium on Discrete Algorithms (New Orleans 2018), pp. 262\u2013273. SIAM, Philadelphia (2018)","DOI":"10.1137\/1.9781611975031.19"},{"key":"569_CR31","unstructured":"Hengeveld, S.B., Miltzow, T.: A practical algorithm with performance guarantees for the art gallery problem. In: 37th International Symposium on Computational Geometry. Leibniz Int. Proc. Inform., vol. 189, #\u00a044. Leibniz-Zent. Inform., Wadern (2021)"},{"key":"569_CR32","doi-asserted-by":"crossref","unstructured":"Kalai, G., Matou\u0161ek, J.: Guarding galleries where every point sees a large area. Isr. J. Math. 101, 125\u2013139 (1997)","DOI":"10.1007\/BF02760925"},{"key":"569_CR33","unstructured":"Katz, M.J.: A PTAS for vertex guarding weakly-visible polygons\u2014an extended abstract (2018). arXiv:1803.02160"},{"issue":"3","key":"569_CR34","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/j.comgeo.2007.02.002","volume":"39","author":"MJ Katz","year":"2008","unstructured":"Katz, M.J., Roisman, G.S.: On guarding the vertices of rectilinear domains. Comput. Geom. 39(3), 219\u2013228 (2008)","journal-title":"Comput. Geom."},{"issue":"3","key":"569_CR35","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/j.comgeo.2012.07.004","volume":"46","author":"J King","year":"2013","unstructured":"King, J.: Fast vertex guarding for polygons with and without holes. Comput. Geom. 46(3), 219\u2013231 (2013)","journal-title":"Comput. Geom."},{"issue":"2","key":"569_CR36","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1007\/s00454-011-9352-x","volume":"46","author":"J King","year":"2011","unstructured":"King, J., Kirkpatrick, D.G.: Improved approximation for guarding simple galleries from the perimeter. Discrete Comput. Geom. 46(2), 252\u2013269 (2011)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"569_CR37","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/s00454-014-9656-8","volume":"53","author":"D Kirkpatrick","year":"2015","unstructured":"Kirkpatrick, D.: An $$O({\\rm lg}\\,{\\rm lg}\\,{ OPT})$$-approximation algorithm for multi-guarding galleries. Discrete Comput. Geom. 53(2), 327\u2013343 (2015)","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"569_CR38","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1016\/0031-3203(92)90093-X","volume":"25","author":"AA Kooshesh","year":"1992","unstructured":"Kooshesh, A.A., Moret, B.M.E.: Three-coloring the vertices of a triangulated simple polygon. Pattern Recognit. 25(4), 443 (1992)","journal-title":"Pattern Recognit."},{"issue":"3","key":"569_CR39","doi-asserted-by":"publisher","first-page":"564","DOI":"10.1007\/s00453-012-9653-3","volume":"66","author":"EA Krohn","year":"2013","unstructured":"Krohn, E.A., Nilsson, B.J.: Approximate guarding of monotone and rectilinear polygons. Algorithmica 66(3), 564\u2013594 (2013)","journal-title":"Algorithmica"},{"issue":"2","key":"569_CR40","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1109\/TIT.1986.1057165","volume":"32","author":"DT Lee","year":"1986","unstructured":"Lee, D.T., Lin, A.K.: Computational complexity of art gallery problems. IEEE Trans. Inform. Theory 32(2), 276\u2013282 (1986)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"569_CR41","doi-asserted-by":"crossref","unstructured":"Niedermeier, R.: Ubiquitous parameterization\u2014invitation to fixed-parameter algorithms. In: 29th International Symposium on Mathematical Foundations of Computer Science (Prague 2004). Lecture Notes in Computer Science, vol. 3153, pp. 84\u2013103. Springer, Berlin (2004)","DOI":"10.1007\/978-3-540-28629-5_4"},{"key":"569_CR42","unstructured":"Niedermeier, R.: Reflections on multivariate algorithmics and problem parameterization. In: 27th International Symposium on Theoretical Aspects of Computer Science (Nancy 2010). Leibniz Int. Proc. Inform., vol.\u00a05, pp. 17\u201332. Leibniz-Zent. Inform., Wadern (2010)"},{"key":"569_CR43","unstructured":"O\u2019Rourke, J.: Art Gallery Theorems and Algorithms. International Series of Monographs on Computer Science. Oxford University Press, Oxford (1987)"},{"issue":"2","key":"569_CR44","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1109\/TIT.1983.1056648","volume":"29","author":"J O\u2019Rourke","year":"1983","unstructured":"O\u2019Rourke, J., Supowit, K.J.: Some NP-hard polygon decomposition problems. IEEE Trans. Inform. Theory 29(2), 181\u2013189 (1983)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"569_CR45","doi-asserted-by":"crossref","unstructured":"de Rezende, P.J., de Souza, C.C., Friedrichs, S., Hemmer, M., Kr\u00f6ller, A., Tozoni, D.C.: Engineering art galleries. In: Algorithm Engineering. Lecture Notes in Computer Science, vol. 9220, pp. 379\u2013417. Springer, Cham (2016)","DOI":"10.1007\/978-3-319-49487-6_12"},{"issue":"2","key":"569_CR46","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1002\/malq.19950410212","volume":"41","author":"D Schuchardt","year":"1995","unstructured":"Schuchardt, D., Hecker, H.-D.: Two NP-hard art-gallery problems for ortho-polygons. Math. Logic Quart. 41(2), 261\u2013267 (1995)","journal-title":"Math. Logic Quart."},{"issue":"9","key":"569_CR47","doi-asserted-by":"publisher","first-page":"1384","DOI":"10.1109\/5.163407","volume":"80","author":"TC Shermer","year":"1992","unstructured":"Shermer, T.C.: Recent results in art galleries. Proc. IEEE 80(9), 1384\u20131399 (1992)","journal-title":"Proc. IEEE"},{"key":"569_CR48","doi-asserted-by":"crossref","unstructured":"Urrutia, J.: Art gallery and illumination problems. In: Handbook of Computational Geometry, pp. 973\u20131027. North-Holland, Amsterdam (2000)","DOI":"10.1016\/B978-044482537-7\/50023-1"},{"issue":"1","key":"569_CR49","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02897056","volume":"104","author":"P Valtr","year":"1998","unstructured":"Valtr, P.: Guarding galleries where no point sees a small area. Isr. J. Math 104(1), 1\u201316 (1998)","journal-title":"Isr. J. Math"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00569-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-023-00569-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00569-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,3]],"date-time":"2024-02-03T23:04:17Z","timestamp":1707001457000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-023-00569-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,5]]},"references-count":49,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,3]]}},"alternative-id":["569"],"URL":"https:\/\/doi.org\/10.1007\/s00454-023-00569-y","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2023,12,5]]},"assertion":[{"value":"9 November 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 November 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 December 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 December 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}