{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T11:13:42Z","timestamp":1778498022435,"version":"3.51.4"},"publisher-location":"New York, NY, USA","reference-count":70,"publisher":"ACM","license":[{"start":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T00:00:00Z","timestamp":1529452800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100008394","name":"Det Frie Forskningsr\u00e5d","doi-asserted-by":"publisher","award":["DFF-0602-02499B"],"award-info":[{"award-number":["DFF-0602-02499B"]}],"id":[{"id":"10.13039\/100008394","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100008394","name":"Natur og Univers, Det Frie Forskningsr\u00e5d","doi-asserted-by":"publisher","award":["DFF-MOBILEX"],"award-info":[{"award-number":["DFF-MOBILEX"]}],"id":[{"id":"10.13039\/100008394","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"European Research Council","doi-asserted-by":"publisher","award":["280152"],"award-info":[{"award-number":["280152"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2018,6,20]]},"DOI":"10.1145\/3188745.3188868","type":"proceedings-article","created":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T20:15:46Z","timestamp":1529525746000},"page":"65-73","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":36,"title":["The art gallery problem is \u2203 \u211d-complete"],"prefix":"10.1145","author":[{"given":"Mikkel","family":"Abrahamsen","sequence":"first","affiliation":[{"name":"University of Copenhagen, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anna","family":"Adamaszek","sequence":"additional","affiliation":[{"name":"University of Copenhagen, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tillmann","family":"Miltzow","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Libre de Bruxelles, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,6,20]]},"reference":[{"key":"e_1_3_2_2_1_1","volume-title":"Schardl","author":"Abel Zachary","year":"2016"},{"key":"e_1_3_2_2_2_1","volume-title":"Hardness of Plane Graph Rigidity. In 32nd International Symposium on Computational Geometry (SoCG","author":"Who Needs","year":"2016"},{"key":"e_1_3_2_2_3_1","volume-title":"33rd International Symposium on Computational Geometry (SoCG 2017)","author":"Abrahamsen Mikkel","year":"2017"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188868"},{"key":"e_1_3_2_2_5_1","unstructured":"Alok Aggarwal. 1984.  Alok Aggarwal. 1984."},{"key":"e_1_3_2_2_7_1","volume-title":"Ullman","author":"Aho Alfred V.","year":"1975"},{"key":"e_1_3_2_2_8_1","unstructured":"The design and analysis of computer algorithms. Addison-Wesley.   The design and analysis of computer algorithms. Addison-Wesley."},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/235809.235813"},{"key":"e_1_3_2_2_10_1","unstructured":"Saugata Basu Richard Pollack and Marie-Fran\u00e7oise Roy. 2006.  Saugata Basu Richard Pollack and Marie-Fran\u00e7oise Roy. 2006."},{"key":"e_1_3_2_2_11_1","unstructured":"Algorithms in real algebraic geometry. Springer-Verlag Berlin Heidelberg.  Algorithms in real algebraic geometry. Springer-Verlag Berlin Heidelberg."},{"key":"e_1_3_2_2_12_1","unstructured":"Patrice Belleville. 1991.  Patrice Belleville. 1991."},{"key":"e_1_3_2_2_13_1","volume-title":"Master\u2019s thesis","author":"Computing"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574701"},{"key":"e_1_3_2_2_15_1","volume-title":"Parameterized Hardness of Art Gallery Problems. In 24th Annual European Symposium on Algorithms (ESA). 19:1\u201319:17","author":"Bonnet \u00c9douard","year":"2016"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2462356.2462361"},{"key":"e_1_3_2_2_17_1","volume-title":"Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG","author":"Brod\u00e9n Bj\u00f6rn","year":"2001"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62257"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2852040.2852053"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-016-9831-1"},{"key":"e_1_3_2_2_21_1","unstructured":"Mark de Berg Marc van Kreveld Mark Overmars and Otfried Cheong. 2008.  Mark de Berg Marc van Kreveld Mark Overmars and Otfried Cheong. 2008."},{"key":"e_1_3_2_2_22_1","volume-title":"Algorithms and Applications","author":"Geometry Computational","edition":"3"},{"key":"e_1_3_2_2_23_1","volume-title":"Tozoni","author":"de Rezende Pedro J.","year":"2016"},{"key":"e_1_3_2_2_24_1","volume-title":"Algorithm Engineering \u2013 Selected Results and Surveys","author":"Galleries Engineering Art"},{"key":"e_1_3_2_2_25_1","volume-title":"Devadoss and Joseph O\u2019Rourke","author":"Satyan","year":"2011"},{"key":"e_1_3_2_2_26_1","unstructured":"Discrete and Computational Geometry. Princeton University Press.  Discrete and Computational Geometry. Princeton University Press."},{"key":"e_1_3_2_2_27_1","unstructured":"Michael G. Dobbins Linda Kleist Tillmann Miltzow and Pawe\u0142 Rza \u00b8\u017cewski. 2017.  Michael G. Dobbins Linda Kleist Tillmann Miltzow and Pawe\u0142 Rza \u00b8\u017cewski. 2017."},{"key":"e_1_3_2_2_28_1","volume-title":"Preprint, https:\/\/arxiv.org\/abs\/ 1712.05142","year":"2017"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.05.014"},{"key":"e_1_3_2_2_30_1","unstructured":"Stephan Eidenbenz Christoph Stamm and Peter Widmayer. 2001.  Stephan Eidenbenz Christoph Stamm and Peter Widmayer. 2001."},{"key":"e_1_3_2_2_31_1","volume-title":"79\u2013113","author":"Inapproximability","year":"2001"},{"key":"e_1_3_2_2_32_1","unstructured":"Stephan Friedrichs Michael Hemmer James King and Christiane Schmidt. 2016.  Stephan Friedrichs Michael Hemmer James King and Christiane Schmidt. 2016."},{"key":"e_1_3_2_2_33_1","volume-title":"Discretization, optimal solutions, and PTAS. Journal of Computational Geometry 7, 1","author":"The","year":"2016"},{"key":"e_1_3_2_2_34_1","unstructured":"Jugal Garg Ruta Mehta Vijay V. Vazirani and Sadra Yazdanbod. 2015.  Jugal Garg Ruta Mehta Vijay V. Vazirani and Sadra Yazdanbod. 2015."},{"key":"e_1_3_2_2_35_1","volume-title":"Decision Versions of Multi-player (Symmetric) Nash Equilibria. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP","volume":"9134","author":"Completeness","year":"2015"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873729"},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-014-9656-8"},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9653-3"},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s003710050177"},{"key":"e_1_3_2_2_40_1","volume-title":"Lin","author":"Lee D. T.","year":"1986"},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1986.1057165"},{"key":"e_1_3_2_2_42_1","volume-title":"Extending Plane drawings is \u2203R-complete. In preparation","author":"Lubiw Anna","year":"2017"},{"key":"e_1_3_2_2_43_1","unstructured":"Ji\u0159\u00ed Matou\u0161ek. 2002.  Ji\u0159\u00ed Matou\u0161ek. 2002."},{"key":"e_1_3_2_2_44_1","volume-title":"Graduate Texts in Mathematics","author":"Discrete Geometry Lectures"},{"key":"e_1_3_2_2_45_1","unstructured":"Ji\u0159\u00ed Matou\u0161ek. 2014. Intersection graphs of segments and \u2203R. (2014). Preprint https:\/\/arxiv.org\/abs\/1406.2636.  Ji\u0159\u00ed Matou\u0161ek. 2014. Intersection graphs of segments and \u2203R. (2014). Preprint https:\/\/arxiv.org\/abs\/1406.2636."},{"key":"e_1_3_2_2_46_1","unstructured":"Colin McDiarmid and Tobias M\u00fcller. 2013.  Colin McDiarmid and Tobias M\u00fcller. 2013."},{"key":"e_1_3_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2012.09.004"},{"key":"e_1_3_2_2_48_1","volume-title":"Topology and geometry \u2013 Rohlin seminar, Oleg Y","author":"Mn\u00ebv Nicolai E"},{"key":"e_1_3_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1137\/140990139"},{"key":"e_1_3_2_2_50_1","unstructured":"Joseph O\u2019Rourke. 1987.  Joseph O\u2019Rourke. 1987."},{"key":"e_1_3_2_2_51_1","unstructured":"Art Gallery Theorems and Algorithms. Oxford University Press.   Art Gallery Theorems and Algorithms. Oxford University Press."},{"key":"e_1_3_2_2_52_1","unstructured":"Joseph O\u2019Rourke. 1998.  Joseph O\u2019Rourke. 1998."},{"key":"e_1_3_2_2_53_1","unstructured":"Computational Geometry in C. Cambridge University Press.  Computational Geometry in C. Cambridge University Press."},{"key":"e_1_3_2_2_54_1","volume-title":"Handbook of Discrete and Computational Geometry","author":"O\u2019Rourke Joseph"},{"key":"e_1_3_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1983.1056648"},{"key":"e_1_3_2_2_56_1","volume-title":"The Free Encyclopedia","author":"Wikipedia Quintic","year":"2017"},{"key":"e_1_3_2_2_57_1","volume-title":"org\/wiki\/Quintic_function {Online","year":"2017"},{"key":"e_1_3_2_2_58_1","volume-title":"Ziegler","author":"Richter-Gebert J\u00fcrgen","year":"1995"},{"key":"e_1_3_2_2_59_1","volume-title":"403\u2013412","author":"Bull Realization","year":"1995"},{"key":"e_1_3_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11805-0_32"},{"key":"e_1_3_2_2_61_1","first-page":"461","article-title":"Realizability of graphs and linkages. In Thirty Essays on Geometric Graph Theory, J\u00e1nos Pach (Ed.). Springer-Verlag New York","volume":"23","author":"Schaefer Marcus","year":"2013","journal-title":"Chapter"},{"key":"e_1_3_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-015-9662-0"},{"key":"e_1_3_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19950410212"},{"key":"e_1_3_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.163407"},{"key":"e_1_3_2_2_65_1","volume-title":"A universality theorem for nonnegative matrix factorizations. Preprint, https:\/\/ arxiv.org\/ abs\/ 1606.09068","author":"Shitov Yaroslav","year":"2016"},{"key":"e_1_3_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1080616"},{"key":"e_1_3_2_2_67_1","volume-title":"Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift, Peter Gritzmann and Bernd Sturmfels (Eds.). DIMACS \u2013 Series in Discrete Mathematics and Theoretical Computer Science","author":"Shor Peter W."},{"key":"e_1_3_2_2_68_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40164-0_29"},{"key":"e_1_3_2_2_69_1","unstructured":"Jorge Urrutia. 2000.  Jorge Urrutia. 2000."},{"key":"e_1_3_2_2_70_1","volume-title":"Handbook of Computational Geometry, J.-R","author":"Gallery Art"},{"key":"e_1_3_2_2_71_1","unstructured":"Abstract 1 Introduction 2 The art gallery problem is in R 3 The problem ETR-INV 4 Reduction from ETR-INV to the art gallery problem 5 Concluding Remarks References  Abstract 1 Introduction 2 The art gallery problem is in R 3 The problem ETR-INV 4 Reduction from ETR-INV to the art gallery problem 5 Concluding Remarks References"}],"event":{"name":"STOC '18: Symposium on Theory of Computing","location":"Los Angeles CA USA","acronym":"STOC '18","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188868","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3188745.3188868","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:07:09Z","timestamp":1750212429000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188868"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,20]]},"references-count":70,"alternative-id":["10.1145\/3188745.3188868","10.1145\/3188745"],"URL":"https:\/\/doi.org\/10.1145\/3188745.3188868","relation":{},"subject":[],"published":{"date-parts":[[2018,6,20]]},"assertion":[{"value":"2018-06-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}