{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T12:42:58Z","timestamp":1648989778222},"reference-count":65,"publisher":"Association for Computing Machinery (ACM)","issue":"1","funder":[{"DOI":"10.13039\/501100004836","name":"Danish Council for Independent Research","doi-asserted-by":"crossref","award":["DFF-0602-02499B"]},{"DOI":"10.13039\/100008398","name":"VILLUM Foundation","doi-asserted-by":"crossref","award":["16582"]},{"name":"ERC","award":["280152"]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2022,2,28]]},"abstract":"\n The\n Art Gallery Problem<\/jats:italic>\n (AGP) is a classic problem in computational geometry, introduced in 1973 by Victor Klee. Given a simple polygon \ud4ab and an integer\n k<\/jats:italic>\n , the goal is to decide if there exists a set\n G<\/jats:italic>\n of\n k<\/jats:italic>\n guards<\/jats:italic>\n within \ud4ab such that every point\n p<\/jats:italic>\n \u2208 \ud4ab is seen by at least one guard\n g<\/jats:italic>\n \u2208\n G<\/jats:italic>\n . Each guard corresponds to a point in the polygon \ud4ab, and we say that a guard\n g<\/jats:italic>\n sees<\/jats:italic>\n a point\n p<\/jats:italic>\n if the line segment\n pg<\/jats:italic>\n is contained in \ud4ab.\n <\/jats:p>\n \n We prove that the AGP is \u2203 \u211d-complete, implying that (1) any system of polynomial equations over the real numbers can be encoded as an instance of the AGP, and (2) the AGP is not in the complexity class NP unless NP = \u2203 \u211d. As a corollary of our construction, we prove that for any real algebraic number \u03b1, there is an instance of the AGP where one of the coordinates of the guards equals \u03b1 in any guard set of minimum cardinality. That rules out many natural geometric approaches to the problem, as it shows that any approach based on constructing a finite set of candidate points for placing guards has to include points with coordinates being roots of polynomials with arbitrary degree. As an illustration of our techniques, we show that for every compact semi-algebraic set\n S<\/jats:italic>\n \u2286 [0, 1]\n 2<\/jats:sup>\n , there exists a polygon with corners at rational coordinates such that for every\n p<\/jats:italic>\n \u2208 [0, 1]\n 2<\/jats:sup>\n , there is a set of guards of minimum cardinality containing\n p<\/jats:italic>\n if and only if\n p<\/jats:italic>\n \u2208\n S<\/jats:italic>\n .\n <\/jats:p>\n In the \u2203 \u211d-hardness proof for the AGP, we introduce a new \u2203 \u211d-complete problem ETR-INV. We believe that this problem is of independent interest, as it has already been used to obtain \u2203 \u211d-hardness proofs for other problems.<\/jats:p>","DOI":"10.1145\/3486220","type":"journal-article","created":{"date-parts":[[2021,12,7]],"date-time":"2021-12-07T21:25:51Z","timestamp":1638912351000},"page":"1-70","source":"Crossref","is-referenced-by-count":0,"title":["The Art Gallery Problem is \u2203\u211d-complete"],"prefix":"10.1145","volume":"69","author":[{"given":"Mikkel","family":"Abrahamsen","sequence":"first","affiliation":[{"name":"University of Copenhagen, Denmark"}]},{"given":"Anna","family":"Adamaszek","sequence":"additional","affiliation":[{"name":"University of Copenhagen, Denmark"}]},{"given":"Tillmann","family":"Miltzow","sequence":"additional","affiliation":[{"name":"Utrecht University, Utrecht, The Netherlands"}]}],"member":"320","reference":[{"key":"e_1_3_2_2_2","unstructured":"Umbra \u2014 Dictionary.com. Accessed 14th of March 2017 http:\/\/www.dictionary.com\/browse\/umbra."},{"key":"e_1_3_2_3_2","unstructured":"Pankaj Kumar Agarwal Kurt Mehlhorn and Monique Teillaud. March 13\u201318 2011. Dagstuhl Seminar 11111 Computational Geometry. (March 13\u201318 2011). DOI:10.4230\/DagRep.1.3.19"},{"key":"e_1_3_2_4_2","first-page":"3:1\u20133:15","volume-title":"Proceedings of the 32nd International Symposium on Computational Geometry","author":"Abel Zachary","year":"2016","unstructured":"Zachary Abel, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Jayson Lynch, and Tao B. Schardl. 2016. Who needs crossings? Hardness of plane graph rigidity. In Proceedings of the 32nd International Symposium on Computational Geometry. 3:1\u20133:15."},{"key":"e_1_3_2_5_2","volume-title":"Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science","author":"Abrahamsen Mikkel","year":"2021","unstructured":"Mikkel Abrahamsen. 2021. Covering polygons is even harder. In Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science."},{"key":"e_1_3_2_6_2","first-page":"3:1\u20133:15","volume-title":"Proceedings of the 33rd International Symposium on Computational Geometry","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. 3:1\u20133:15."},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188868"},{"key":"e_1_3_2_8_2","unstructured":"Mikkel Abrahamsen Linda Kleist and Tillmann Miltzow. 2021. Training Neural Networks is ER-complete. In Proceedings of Advances in Neural Information Processing Systems 34 (NeurIPS\u201921) . Retrieved from https:\/\/arxiv.org\/abs\/2102.09798."},{"key":"e_1_3_2_9_2","volume-title":"Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science","author":"Abrahamsen Mikkel","year":"2020","unstructured":"Mikkel Abrahamsen, Tillmann Miltzow, and Nadja Seiferth. 2020. Framework for \u2203\u211d-Completeness of Two-Dimensional packing problems. In Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science. DOI:DOI:https:\/\/doi.org\/10.1109\/FOCS46700.2020.00098"},{"key":"e_1_3_2_10_2","volume-title":"The Art Gallery Theorem: Its Variations, Applications and Algorithmic Aspects","author":"Aggarwal Alok","year":"1984","unstructured":"Alok Aggarwal. 1984. The Art Gallery Theorem: Its Variations, Applications and Algorithmic Aspects. Ph.D. Dissertation. The Johns Hopkins University."},{"key":"e_1_3_2_11_2","volume-title":"The Design and Analysis of Computer Algorithms","author":"Aho Alfred V.","year":"1975","unstructured":"Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. 1975. The Design and Analysis of Computer Algorithms. Addison-Wesley."},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107340749"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/235809.235813"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.5555\/1197095"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2010.06.009"},{"key":"e_1_3_2_16_2","volume-title":"Computing Two-Covers of Simple Polygons","author":"Belleville Patrice","year":"1991","unstructured":"Patrice Belleville. 1991. Computing Two-Covers of Simple Polygons. Master\u2019s thesis. McGill University."},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574701"},{"key":"e_1_3_2_18_2","first-page":"17:1\u201317:13","volume-title":"Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science","author":"Bil\u00f2 Vittorio","year":"2016","unstructured":"Vittorio Bil\u00f2 and Marios Mavronicolas. 2016. A catalog of \u2203\u211d-Complete decision problems about Nash equilibria in multi-player games. In Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science. 17:1\u201317:13. DOI:DOI:https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2016.17"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3398684"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/2462356.2462361"},{"key":"e_1_3_2_21_2","first-page":"45","volume-title":"Proceedings of the 13th Canadian Conference on Computational Geometry","author":"Brod\u00e9n Bj\u00f6rn","year":"2001","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. 45\u201348."},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62257"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/2852040.2852053"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-016-9831-1"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22300-6_20"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.5555\/1370949"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-49487-6_12"},{"key":"e_1_3_2_28_2","volume-title":"Discrete and Computational Geometry","author":"Devadoss Satyan L.","year":"2011","unstructured":"Satyan L. Devadoss and Joseph O\u2019Rourke. 2011. Discrete and Computational Geometry. Princeton University Press."},{"key":"e_1_3_2_29_2","unstructured":"Michael Gene Dobbins Andreas Holmsen and Tillmann Miltzow. 2018. Smoothed analysis of the art gallery problem. arXiv:1811.01177. Retrieved from http:\/\/arxiv.org\/abs\/1811.01177."},{"key":"e_1_3_2_30_2","unstructured":"Michael Gene Dobbins Andreas Holmsen and Tillmann Miltzow. 2019. A universality theorem for nested polytopes. (2019). arXiv:1908.02213. Retrieved from http:\/\/arxiv.org\/abs\/1908.02213."},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-00256-5_14"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.05.014"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0040-8"},{"key":"e_1_3_2_34_2","unstructured":"Jeff Erickson. 2019. Optimal curve straightening is \u2203\u211d-Complete. (2019). arXiv:1908.09400. Retrieved from http:\/\/arxiv.org\/abs\/1908.09400."},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00099"},{"key":"e_1_3_2_36_2","author":"Fekete S\u00e1ndor","unstructured":"S\u00e1ndor Fekete. Private communication. (Accessed 21st of November 2016).","journal-title":"Private communication"},{"issue":"1","key":"e_1_3_2_37_2","first-page":"256","article-title":"The continuous 1.5D terrain guarding problem: Discretization, optimal solutions, and PTAS","volume":"7","author":"Friedrichs Stephan","year":"2016","unstructured":"Stephan Friedrichs, Michael Hemmer, James King, and Christiane Schmidt. 2016. The continuous 1.5D terrain guarding problem: Discretization, optimal solutions, and PTAS. Journal of Computational Geometry 7, 1 (2016), 256\u2013284.","journal-title":"Journal of Computational Geometry"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_45"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.128"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-014-9656-8"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9653-3"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1007\/s003710050177"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1986.1057165"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-04414-5_28"},{"key":"e_1_3_2_45_2","unstructured":"Maple 2016.1 Maplesoft a division of Waterloo Maple Inc. Waterloo Ontario. Maple is a trademark of Waterloo Maple Inc. (Accessed 23rd of March 2017)."},{"key":"e_1_3_2_46_2","unstructured":"Ji\u0159\u00ed Matou\u0161ek. 2014. Intersection graphs of segments and \u2203\u211d. (2014). Lecture notes. arxiv.org\/abs\/1406.2636. Retrieved from https:\/\/arxiv.org\/abs\/1406.2636."},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2012.09.004"},{"key":"e_1_3_2_48_2","volume-title":"Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science","author":"Miltzow Tillmann","year":"2021","unstructured":"Tillmann Miltzow and Reinier F. Schmiermann. 2021. On classifying continuous constraint satisfaction problems. In Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science."},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0082792"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1137\/140990139"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.5555\/40599"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.5555\/521378"},{"key":"e_1_3_2_53_2","volume-title":"Handbook of Discrete and Computational Geometry (second ed.)","author":"O\u2019Rourke Joseph","year":"2004","unstructured":"Joseph O\u2019Rourke. 2004. Visibility. In Handbook of Discrete and Computational Geometry (second ed.), Jacob E. Goodman and Joseph O\u2019Rourke (Eds.), Chapman & Hall\/CRC, Chapter 28."},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1983.1056648"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-1995-00604-X"},{"key":"e_1_3_2_56_2","unstructured":"G\u00fcnter Rote. 2011. EuroCG Open Problem Session. (2011). See the personal webpage of G\u00fcnter Rote: Retrieved from http:\/\/page.mi.fu-berlin.de\/rote\/Papers\/slides\/Open-Problem_artgallery-Morschach-EuroCG-2011.pdf."},{"key":"e_1_3_2_57_2","first-page":"334","volume-title":"Proceedings of the 17th International Symposium on Graph Drawing","author":"Schaefer Marcus","year":"2009","unstructured":"Marcus Schaefer. 2009. Complexity of some geometric and topological problems. In Proceedings of the 17th International Symposium on Graph Drawing. 334\u2013344."},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-0110-0_24"},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-015-9662-0"},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19950410212"},{"key":"e_1_3_2_61_2","doi-asserted-by":"publisher","DOI":"10.1109\/5.163407"},{"key":"e_1_3_2_62_2","unstructured":"Yaroslav Shitov. 2016. A universality theorem for nonnegative matrix factorizations. (2016). arxiv.org\/abs\/1606.09068. Retrieved from https:\/\/arxiv.org\/abs\/1606.09068."},{"key":"e_1_3_2_63_2","doi-asserted-by":"publisher","DOI":"10.1137\/16M1080616"},{"key":"e_1_3_2_64_2","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/004\/41"},{"key":"e_1_3_2_65_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40164-0_29"},{"key":"e_1_3_2_66_2","doi-asserted-by":"publisher","DOI":"10.1016\/B978-044482537-7\/50023-1"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3486220","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,10]],"date-time":"2022-02-10T15:09:39Z","timestamp":1644505779000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3486220"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,28]]},"references-count":65,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,2,28]]}},"alternative-id":["10.1145\/3486220"],"URL":"http:\/\/dx.doi.org\/10.1145\/3486220","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[2022,2,28]]}}}