{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T03:11:05Z","timestamp":1784257865683,"version":"3.55.0"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2020,6,21]],"date-time":"2020-06-21T00:00:00Z","timestamp":1592697600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"supporteNetherlands Organisation for Scientific Research","award":["016.Veni.192.250."],"award-info":[{"award-number":["016.Veni.192.250."]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2020,10,31]]},"abstract":"<jats:p>\n            Given a simple polygon\n            <jats:italic>P<\/jats:italic>\n            on\n            <jats:italic>n<\/jats:italic>\n            vertices, two points\n            <jats:italic>x<\/jats:italic>\n            ,\n            <jats:italic>y<\/jats:italic>\n            in\n            <jats:italic>P<\/jats:italic>\n            are said to be visible to each other if the line segment between\n            <jats:italic>x<\/jats:italic>\n            and\n            <jats:italic>y<\/jats:italic>\n            is contained in\n            <jats:italic>P<\/jats:italic>\n            . The P\n            <jats:sc>oint<\/jats:sc>\n            G\n            <jats:sc>uard<\/jats:sc>\n            A\n            <jats:sc>rt<\/jats:sc>\n            G\n            <jats:sc>allery<\/jats:sc>\n            problem asks for a minimum set\n            <jats:italic>S<\/jats:italic>\n            such that every point in\n            <jats:italic>P<\/jats:italic>\n            is visible from a point in\n            <jats:italic>S<\/jats:italic>\n            . The V\n            <jats:sc>ertex<\/jats:sc>\n            G\n            <jats:sc>uard<\/jats:sc>\n            A\n            <jats:sc>rt<\/jats:sc>\n            G\n            <jats:sc>allery<\/jats:sc>\n            problem asks for such a set\n            <jats:italic>S<\/jats:italic>\n            subset of the vertices of\n            <jats:italic>P<\/jats:italic>\n            . A point in the set\n            <jats:italic>S<\/jats:italic>\n            is referred to as a guard. For both variants, we rule out any\n            <jats:italic>f<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            )\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>o<\/jats:italic>\n              (\n              <jats:italic>k<\/jats:italic>\n              \/ log\n              <jats:italic>k<\/jats:italic>\n              )\n            <\/jats:sup>\n            algorithm, where\n            <jats:italic>k<\/jats:italic>\n            := |\n            <jats:italic>S<\/jats:italic>\n            | is the number of guards, for any computable function\n            <jats:italic>f<\/jats:italic>\n            , unless the exponential time hypothesis fails. These lower bounds almost match the\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (\n              <jats:italic>k<\/jats:italic>\n              )\n            <\/jats:sup>\n            algorithms that exist for both problems.\n          <\/jats:p>","DOI":"10.1145\/3398684","type":"journal-article","created":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T02:39:25Z","timestamp":1592793565000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Parameterized Hardness of Art Gallery Problems"],"prefix":"10.1145","volume":"16","author":[{"given":"\u00c9douard","family":"Bonnet","sequence":"first","affiliation":[{"name":"Universit\u00e9 de Lyon, ENS Lyon, all\u00e9e d\u2019Italie, Lyon"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tillmann","family":"Miltzow","sequence":"additional","affiliation":[{"name":"Utrecht University, Princetonplein, Utrecht, Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,21]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 33rd International Symposium on Computational Geometry (SoCG \u201917)","author":"Abrahamsen Mikkel","year":"2017","unstructured":"Mikkel Abrahamsen , Anna Adamaszek , and Tillmann Miltzow . 2017 . Irrational guards are sometimes needed . In Proceedings of the 33rd International Symposium on Computational Geometry (SoCG \u201917) . Article 3, 15 pages. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.SoCG. 2017.3 10.4230\/LIPIcs.SoCG.2017.3 Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow. 2017. Irrational guards are sometimes needed. In Proceedings of the 33rd International Symposium on Computational Geometry (SoCG \u201917). Article 3, 15 pages. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2017.3"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188868"},{"key":"e_1_2_1_4_1","unstructured":"Akanksha Agrawal Pradeesha Ashok Meghana M. Reddy Saket Saurabh and Dolly Yadav. 2019. FPT algorithms for conflict-free coloring of graphs and chromatic terrain guarding. arXiv:1905.01822.  Akanksha Agrawal Pradeesha Ashok Meghana M. Reddy Saket Saurabh and Dolly Yadav. 2019. FPT algorithms for conflict-free coloring of graphs and chromatic terrain guarding. arXiv:1905.01822."},{"key":"e_1_2_1_5_1","volume-title":"The parameterized complexity of guarding almost convex polygons. To appear in the 36th International Symposium on Computational Geometry (SoCG\u201920)","author":"Agrawal Akanksha","unstructured":"Akanksha Agrawal , Kristine Knudsen , Daniel Lokshtanov , Saket Saurabh , and Meirav Zehavi . 2020. The parameterized complexity of guarding almost convex polygons. To appear in the 36th International Symposium on Computational Geometry (SoCG\u201920) . Akanksha Agrawal, Kristine Knudsen, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. 2020. The parameterized complexity of guarding almost convex polygons. To appear in the 36th International Symposium on Computational Geometry (SoCG\u201920)."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186897"},{"key":"e_1_2_1_7_1","volume-title":"Katz","author":"Ashur Stav","year":"2019","unstructured":"Stav Ashur , Omrit Filtser , and Matthew J . Katz . 2019 . A constant-factor approximation algorithm for vertex guarding a WV-Polygon . arXiv:1907.01228. Stav Ashur, Omrit Filtser, and Matthew J. Katz. 2019. A constant-factor approximation algorithm for vertex guarding a WV-Polygon. arXiv:1907.01228."},{"key":"e_1_2_1_8_1","volume-title":"Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics","author":"Basu Saugata","unstructured":"Saugata Basu , Richard Pollack , and Marie-Francoise Roy . 2011. Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics . Vol. 10 . Springer . Saugata Basu, Richard Pollack, and Marie-Francoise Roy. 2011. Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics. Vol. 10. Springer."},{"key":"e_1_2_1_9_1","volume-title":"Subir Kumar Ghosh, and Sudebkumar Pal","author":"Bhattacharya Pritam","year":"2017","unstructured":"Pritam Bhattacharya , Subir Kumar Ghosh, and Sudebkumar Pal . 2017 . Constant approximation algorithms for guarding simple polygons using vertex guards. arXiv:1712.05492. Pritam Bhattacharya, Subir Kumar Ghosh, and Sudebkumar Pal. 2017. Constant approximation algorithms for guarding simple polygons using vertex guards. arXiv:1712.05492."},{"key":"e_1_2_1_10_1","first-page":"21","article-title":"Orthogonal terrain guarding is NP-complete","volume":"10","author":"Bonnet \u00c9douard","year":"2019","unstructured":"\u00c9douard Bonnet and Panos Giannopoulos . 2019 . Orthogonal terrain guarding is NP-complete . Journal of Computational Geometry 10 , 2 (2019), 21 -- 44 . DOI:https:\/\/doi.org\/10.20382\/jocg.v10i2a3 10.20382\/jocg.v10i2a3 \u00c9douard Bonnet and Panos Giannopoulos. 2019. Orthogonal terrain guarding is NP-complete. Journal of Computational Geometry 10, 2 (2019), 21--44. DOI:https:\/\/doi.org\/10.20382\/jocg.v10i2a3","journal-title":"Journal of Computational Geometry"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 12th International Symposium on Parameterized and Exact Computation (IPEC\u201917)","author":"Bonnet \u00c9douard","year":"2017","unstructured":"\u00c9douard Bonnet , Panos Giannopoulos , and Michael Lampis . 2017 . On the parameterized complexity of red-blue points separation . In Proceedings of the 12th International Symposium on Parameterized and Exact Computation (IPEC\u201917) . Article 8, 13 pages. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.IPEC. 2017.8 10.4230\/LIPIcs.IPEC.2017.8 \u00c9douard Bonnet, Panos Giannopoulos, and Michael Lampis. 2017. On the parameterized complexity of red-blue points separation. In Proceedings of the 12th International Symposium on Parameterized and Exact Computation (IPEC\u201917). Article 8, 13 pages. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2017.8"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 33rd International Symposium on Computational Geometry (SoCG\u201917)","author":"Bonnet \u00c9douard","year":"2017","unstructured":"\u00c9douard Bonnet and Tillmann Miltzow . 2017 . An approximation algorithm for the art gallery problem . In Proceedings of the 33rd International Symposium on Computational Geometry (SoCG\u201917) . Article 20, 15 pages. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.SoCG. 2017.20 10.4230\/LIPIcs.SoCG.2017.20 \u00c9douard Bonnet and Tillmann Miltzow. 2017. An approximation algorithm for the art gallery problem. In Proceedings of the 33rd International Symposium on Computational Geometry (SoCG\u201917). Article 20, 15 pages. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2017.20"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 13th Canadian Conference on Computational Geometry.","author":"Brod\u00e9n Bj\u00f6rn","unstructured":"Bj\u00f6rn Brod\u00e9n , Mikael Hammar , and Bengt J. Nilsson . 2001. Guarding lines and 2-link polygons is APX-hard . In Proceedings of the 13th Canadian Conference on Computational Geometry. Bj\u00f6rn Brod\u00e9n, Mikael Hammar, and Bengt J. Nilsson. 2001. Guarding lines and 2-link polygons is APX-hard. In Proceedings of the 13th Canadian Conference on Computational Geometry."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.04.007"},{"key":"e_1_2_1_15_1","volume-title":"Parameterized Algorithms","author":"Cygan Marek","unstructured":"Marek Cygan , Fedor V. Fomin , Lukasz Kowalik , Daniel Lokshtanov , D\u00e1niel Marx , Marcin Pilipczuk , Michal Pilipczuk , and Saket Saurabh . 2015. Parameterized Algorithms . Springer . DOI:https:\/\/doi.org\/10.1007\/978-3-319-21275-3 10.1007\/978-3-319-21275-3 Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D\u00e1niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer. DOI:https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"key":"e_1_2_1_16_1","volume-title":"Tozoni","author":"de Rezende Pedro J.","year":"2016","unstructured":"Pedro J. de Rezende , Cid C. de Souza , Stephan Friedrichs , Michael Hemmer , Alexander Kr\u00f6ller , and Davi C . Tozoni . 2016 . Engineering art galleries. In Algorithm\u00a0Engineering. Springer , 379--417. Pedro J. de Rezende, Cid C. de Souza, Stephan Friedrichs, Michael Hemmer, Alexander Kr\u00f6ller, and Davi C. Tozoni. 2016. Engineering art galleries. In Algorithm\u00a0Engineering. Springer, 379--417."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9471-4"},{"key":"e_1_2_1_18_1","volume-title":"Downey and Michael Ralph Fellows","author":"Rodney","year":"2012","unstructured":"Rodney G. Downey and Michael Ralph Fellows . 2012 . Parameterized Complexity. Springer Science 8 Business Media. Rodney G. Downey and Michael Ralph Fellows. 2012. Parameterized Complexity. Springer Science 8 Business Media."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.05.014"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0040-8"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 33rd International Symposium on Computational Geometry (SoCG\u201917)","author":"Elbassioni Khaled","year":"2017","unstructured":"Khaled Elbassioni . 2017 . Finding small hitting sets in infinite range spaces of bounded VC-dimension . In Proceedings of the 33rd International Symposium on Computational Geometry (SoCG\u201917) . Article 40, 15 pages. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.SoCG. 2017.40 10.4230\/LIPIcs.SoCG.2017.40 Khaled Elbassioni. 2017. Finding small hitting sets in infinite range spaces of bounded VC-dimension. In Proceedings of the 33rd International Symposium on Computational Geometry (SoCG\u201917). Article 40, 15 pages. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2017.40"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(78)90059-X"},{"key":"e_1_2_1_23_1","series-title":"An EATCS Series","volume-title":"Parameterized Complexity Theory. Texts in Theoretical Computer Science","author":"Flum J\u00f6rg","unstructured":"J\u00f6rg Flum and Martin Grohe . 2006. Parameterized Complexity Theory. Texts in Theoretical Computer Science . An EATCS Series . Vol. XIV . Springer . J\u00f6rg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Vol. XIV. Springer."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2009.12.004"},{"key":"e_1_2_1_25_1","volume-title":"Algorithms and Computation","author":"Gibson Matt","unstructured":"Matt Gibson , Erik Krohn , and Qing Wang . 2015. The VC-dimension of visibility on the boundary of a simple polygon . In Algorithms and Computation . Springer , 541--551. Matt Gibson, Erik Krohn, and Qing Wang. 2015. The VC-dimension of visibility on the boundary of a simple polygon. In Algorithms and Computation. Springer, 541--551."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2013.08.012"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.1999.766282"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.09.001"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02760925"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2007.02.002"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2012.07.004"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/100791506"},{"key":"e_1_2_1_33_1","volume-title":"Discrete 8 Computational Geometry 53, 2","author":"Kirkpatrick David G.","year":"2015","unstructured":"David G. Kirkpatrick . 2015. An O(lg lg OPT)-approximation algorithm for multi-guarding galleries. Discrete 8 Computational Geometry 53, 2 ( 2015 ), 327--343. DOI:https:\/\/doi.org\/10.1007\/s00454-014-9656-8 10.1007\/s00454-014-9656-8 David G. Kirkpatrick. 2015. An O(lg lg OPT)-approximation algorithm for multi-guarding galleries. Discrete 8 Computational Geometry 53, 2 (2015), 327--343. DOI:https:\/\/doi.org\/10.1007\/s00454-014-9656-8"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9653-3"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1986.1057165"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2010.v006a005"},{"key":"e_1_2_1_37_1","volume-title":"Algorithms\u2014ESA","author":"Marx D\u00e1niel","year":"2015","unstructured":"D\u00e1niel Marx and Michal Pilipczuk . 2015. Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams . In Algorithms\u2014ESA 2015 . Lecture Notes in Computer Science, Vol. 9294 . Springer , 865--877. DOI:https:\/\/doi.org\/10.1007\/978-3-662-48350-3_72 10.1007\/978-3-662-48350-3_72 D\u00e1niel Marx and Michal Pilipczuk. 2015. Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams. In Algorithms\u2014ESA 2015. Lecture Notes in Computer Science, Vol. 9294. Springer, 865--877. DOI:https:\/\/doi.org\/10.1007\/978-3-662-48350-3_72"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(90)90017-F"},{"key":"e_1_2_1_39_1","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"Niedermeier Rolf","unstructured":"Rolf Niedermeier . 2006. Invitation to Fixed-Parameter Algorithms . Oxford University Press . Rolf Niedermeier. 2006. Invitation to Fixed-Parameter Algorithms. Oxford University Press."},{"key":"e_1_2_1_40_1","volume-title":"Art Gallery Theorems and Algorithms","author":"O\u2019Rourke Joseph","unstructured":"Joseph O\u2019Rourke . 1987. Art Gallery Theorems and Algorithms . Vol. 57 . Oxford University Press Oxford . Joseph O\u2019Rourke. 1987. Art Gallery Theorems and Algorithms. Vol. 57. Oxford University Press Oxford."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02897056"},{"key":"e_1_2_1_42_1","unstructured":"Michael Gene Dobbins Andreas Holmsen and Tillmann Miltzow. 2018. Smoothed analysis of the art gallery problem. CoRR abs\/1811.01177. http:\/\/arxiv.org\/abs\/1811.01177.  Michael Gene Dobbins Andreas Holmsen and Tillmann Miltzow. 2018. Smoothed analysis of the art gallery problem. CoRR abs\/1811.01177. http:\/\/arxiv.org\/abs\/1811.01177."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3398684","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3398684","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:33:31Z","timestamp":1750199611000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3398684"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,21]]},"references-count":41,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,10,31]]}},"alternative-id":["10.1145\/3398684"],"URL":"https:\/\/doi.org\/10.1145\/3398684","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,21]]},"assertion":[{"value":"2019-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-06-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}