{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T11:13:52Z","timestamp":1778498032119,"version":"3.51.4"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2023,8,27]],"date-time":"2023-08-27T00:00:00Z","timestamp":1693094400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,8,27]],"date-time":"2023-08-27T00:00:00Z","timestamp":1693094400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["016.Veni.192.250"],"award-info":[{"award-number":["016.Veni.192.250"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100011102","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["ERC StG 716424"],"award-info":[{"award-number":["ERC StG 716424"]}],"id":[{"id":"10.13039\/100011102","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2024,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Let <jats:italic>P<\/jats:italic> be a simple polygon, then the art gallery problem is looking for a minimum set of points (guards) that can see every point in\u00a0<jats:italic>P<\/jats:italic>. We say two points <jats:inline-formula><jats:alternatives><jats:tex-math>$$a,b\\in P$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>a<\/mml:mi>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mi>b<\/mml:mi>\n                    <mml:mo>\u2208<\/mml:mo>\n                    <mml:mi>P<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> can see each other if the line segment <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\text {seg}} (a,b)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mtext>seg<\/mml:mtext>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>a<\/mml:mi>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mi>b<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is contained in\u00a0<jats:italic>P<\/jats:italic>. We denote by <jats:italic>V<\/jats:italic>(<jats:italic>P<\/jats:italic>) the family of all minimum guard placements. The Hausdorff distance makes <jats:italic>V<\/jats:italic>(<jats:italic>P<\/jats:italic>) a metric space and thus a topological space. We show homotopy-universality, that is, for every semi-algebraic set <jats:italic>S<\/jats:italic> there is a polygon <jats:italic>P<\/jats:italic> such that <jats:italic>V<\/jats:italic>(<jats:italic>P<\/jats:italic>) is homotopy equivalent to\u00a0<jats:italic>S<\/jats:italic>. Furthermore, for various concrete topological spaces <jats:italic>T<\/jats:italic>, we describe instances <jats:italic>I<\/jats:italic> of the art gallery problem such that <jats:italic>V<\/jats:italic>(<jats:italic>I<\/jats:italic>) is homeomorphic to\u00a0<jats:italic>T<\/jats:italic>.<\/jats:p>","DOI":"10.1007\/s00454-023-00540-x","type":"journal-article","created":{"date-parts":[[2023,8,27]],"date-time":"2023-08-27T18:01:25Z","timestamp":1693159285000},"page":"1092-1130","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Topological Art in Simple Galleries"],"prefix":"10.1007","volume":"71","author":[{"given":"Daniel","family":"Bertschinger","sequence":"first","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1037-0203","authenticated-orcid":false,"given":"Nicolas","family":"El Maalouly","sequence":"additional","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4563-2864","authenticated-orcid":false,"given":"Tillmann","family":"Miltzow","sequence":"additional","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2172-9285","authenticated-orcid":false,"given":"Patrick","family":"Schnider","sequence":"additional","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1901-3621","authenticated-orcid":false,"given":"Simon","family":"Weber","sequence":"additional","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,8,27]]},"reference":[{"key":"540_CR1","unstructured":"Abrahamsen, M.: Constant-Workspace Algorithms for Visibility Problems in the Plane. MSc thesis, University of Copenhagen (2013). http:\/\/hjemmesider.diku.dk\/~jyrki\/PE-lab\/Mikkel\/thesis.pdf"},{"key":"540_CR2","unstructured":"Abrahamsen, M., Adamaszek, A., Miltzow, T.: Irrational guards are sometimes needed. In: 33rd International Symposium on Computational Geometry (Brisbane 2017). Leibniz International Proceedings in Informatics, vol. 77, #\u00a03. Leibniz-Zent. Inform., Wadern (2017)"},{"key":"540_CR3","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":"540_CR4","unstructured":"Abrahamsen, M., Kleist, L., Miltzow, T.: Geometric embeddability of complexes is $$\\exists {\\mathbb{R}}$$-complete (2021). arXiv:2108.02585"},{"key":"540_CR5","unstructured":"Abrahamsen, M., Kleist, L., Miltzow, T.: Training neural networks is ER-complete. In: Advances in Neural Information Processing Systems (NIPS), vol.\u00a034, pp. 18293\u201318306. Curran Associates, Red Hook (2021)"},{"key":"540_CR6","unstructured":"Agrawal, A., Knudsen, K.V.K., Lokshtanov, D., Saurabh, S., Zehavi, M.: The parameterized complexity of guarding almost convex polygons. In: 36th International Symposium on Computational Geometry (2020). Leibniz International Proceedings in Informatics, vol. 164, #\u00a03. Leibniz-Zent. Inform., Wadern (2020)"},{"key":"540_CR7","doi-asserted-by":"crossref","unstructured":"Agrawal, A., Zehavi, M.: Parameterized analysis of art gallery and terrain guarding. In: Computer Science\u2014Theory and Applications (Yekaterinburg 2020). Lecture Notes in Computer Science, vol. 12159, pp. 16\u201329. Springer, Cham (2020)","DOI":"10.1007\/978-3-030-50026-9_2"},{"key":"540_CR8","doi-asserted-by":"crossref","unstructured":"Ashok, P., Reddy, M.M.: Efficient guarding of polygons and terrains. In: 13th International Workshop on Frontiers in Algorithmics (Sanya 2019). Lecture Notes in Computer Science, vol. 11458, pp. 26\u201337. Springer, Cham (2019)","DOI":"10.1007\/978-3-030-18126-0_3"},{"issue":"5","key":"540_CR9","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1007\/BF02574701","volume":"6","author":"D Bienstock","year":"1991","unstructured":"Bienstock, D.: Some provably hard crossing number problems. Discrete Comput. Geom. 6(5), 443\u2013459 (1991)","journal-title":"Discrete Comput. Geom."},{"key":"540_CR10","series-title":"Encyclopedia of Mathematics and Its Applications","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511586507","volume-title":"Oriented Matroids","author":"A Bj\u00f6rner","year":"1999","unstructured":"Bj\u00f6rner, A., Las Vergnas, M., Sturmfels, B., White, N., Ziegler, G.M.: Oriented Matroids. Encyclopedia of Mathematics and Its Applications, vol. 46. Cambridge University Press, Cambridge (1999)"},{"key":"540_CR11","unstructured":"Blass, J., Holszty\u0144ski, W.: Cubical polyhedra and homotopy, III. Atti Accad. Naz. Lincei Rend. Cl. Sci. Fis. Mat. Nat. 53 (3\u20134), 275\u2013279 (1972)"},{"key":"540_CR12","unstructured":"Bonnet, \u00c9., Miltzow, T.: An approximation algorithm for the art gallery problem. In: 33rd International Symposium on Computational Geometry (Brisbane 2017). Leibniz International Proceedings in Informatics, vol. 77, #\u00a020. Leibniz-Zent. Inform., Wadern (2017)"},{"key":"540_CR13","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":"540_CR14","doi-asserted-by":"crossref","unstructured":"Borrmann, D., de Rezende, P.J., de Souza, C.C., Fekete, S.P., Friedrichs, S., Kr\u00f6ller,\u00a0A., N\u00fcchter,\u00a0A., Schmidt, Ch., Tozoni, D.C.: Point guards and point clouds: solving general art gallery problems. In: 29th Annual Symposium on Computational Geometry (Rio de Janeiro 2013), pp. 347\u2013348. ACM, New York (2013)","DOI":"10.1145\/2493132.2462361"},{"issue":"4","key":"540_CR15","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1145\/2852040.2852053","volume":"46","author":"J Cardinal","year":"2015","unstructured":"Cardinal, J.: Computational geometry column 62. ACM SIGACT News 46(4), 69\u201378 (2015)","journal-title":"ACM SIGACT News"},{"key":"540_CR16","doi-asserted-by":"crossref","unstructured":"Cardinal, J., Felsner, S., Miltzow, T., Tompkins, C., Vogtenhuber, B.: Intersection graphs of rays and grounded segments. In: Graph-Theoretic Concepts in Computer Science (Eindhoven 2017). Lecture Notes in Computer Science, vol. 10520, pp. 153\u2013166. Springer, Cham (2017)","DOI":"10.1007\/978-3-319-68705-6_12"},{"issue":"1","key":"540_CR17","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0095-8956(75)90061-1","volume":"18","author":"V Chv\u00e1tal","year":"1975","unstructured":"Chv\u00e1tal, V.: A combinatorial theorem in plane geometry. J. Combin. Theory Ser. B 18(1), 39\u201341 (1975)","journal-title":"J. Combin. Theory Ser. B"},{"key":"540_CR18","unstructured":"Dobbins, M.G., Holmsen, A., Miltzow, T.: Smoothed analysis of the art gallery problem (2018). arXiv:1811.01177"},{"key":"540_CR19","doi-asserted-by":"crossref","unstructured":"Efrat, A., Har-Peled, S.: Guarding galleries and terrains. In: Foundations of Information Technology in the Era of Network and Mobile Computing (Montr\u00e9al 2002). IFIP Advances in Information and Communication Technology, vol. 96, pp. 181\u2013192. Springer, New York (2002)","DOI":"10.1007\/978-0-387-35608-2_16"},{"issue":"1","key":"540_CR20","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":"2","key":"540_CR21","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1016\/0196-6774(81)90019-5","volume":"2","author":"H El-Gindy","year":"1981","unstructured":"El-Gindy, H., Avis, D.: A linear algorithm for computing the visibility polygon from a point. J.\u00a0Algorithms 2(2), 186\u2013197 (1981)","journal-title":"J.\u00a0Algorithms"},{"key":"540_CR22","doi-asserted-by":"crossref","unstructured":"Erickson, J., van der Hoog, I., Miltzow, T.: Smoothing the gap between NP and ER. In: 61st Annual Symposium on Foundations of Computer Science (Durham 2020), pp. 1022\u20131033. IEEE Computer Society, Los Alamitos (2020)","DOI":"10.1109\/FOCS46700.2020.00099"},{"issue":"3","key":"540_CR23","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. Combin. Theory Ser. B 24(3), 374 (1978)","journal-title":"J. Combin. Theory Ser. B"},{"key":"540_CR24","unstructured":"Friedrichs, S.: Integer Solutions for the Art Gallery Problem Using Linear Programming. MSc thesis, TU Braunschweig (2012)"},{"key":"540_CR25","volume-title":"Algebraic Topology","author":"A Hatcher","year":"2002","unstructured":"Hatcher, A.: Algebraic Topology. Cambridge University Press, Cambridge (2002)"},{"issue":"1","key":"540_CR26","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1137\/S0097539791221505","volume":"24","author":"PJ Heffernan","year":"1995","unstructured":"Heffernan, P.J., Mitchell, J.S.B.: An optimal algorithm for computing visibility in the plane. SIAM J. Comput. 24(1), 184\u2013201 (1995)","journal-title":"SIAM J. Comput."},{"key":"540_CR27","unstructured":"Hengeveld, S.B., Miltzow, T.: A practical algorithm with performance guarantees for the art gallery problem. In: 37th International Symposium on Computational Geometry (2021). Leibniz International Proceedings in Informatics, vol. 189, #\u00a044. Leibniz-Zent. Inform., Wadern (2021)"},{"key":"540_CR28","doi-asserted-by":"crossref","unstructured":"Hironaka, H.: Triangulations of algebraic sets. In: Algebraic Geometry (Arcata 1974). Proceedings of Symposia in Pure Mathematics, vol. 29, pp. 165\u2013185. American Mathematical Society, Providence (1975)","DOI":"10.1090\/pspum\/029\/0374131"},{"issue":"2","key":"540_CR29","doi-asserted-by":"publisher","first-page":"183","DOI":"10.7155\/jgaa.00411","volume":"21","author":"U Hoffmann","year":"2017","unstructured":"Hoffmann, U.: On the complexity of the planar slope number problem. J. Graph Algorithms Appl. 21(2), 183\u2013193 (2017)","journal-title":"J. Graph Algorithms Appl."},{"key":"540_CR30","unstructured":"Hofmann, K.R.: Triangulation of Locally Semi-Algebraic Spaces. PhD thesis, University of Michigan (2009)"},{"key":"540_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-55611-7","volume-title":"Axioms and Hulls","author":"DE Knuth","year":"1992","unstructured":"Knuth, D.E.: Axioms and Hulls. Lecture Notes in Computer Science, vol. 606. Springer, Berlin (1992)"},{"issue":"2","key":"540_CR32","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":"540_CR33","unstructured":"Matou\u0161ek, J.: Intersection graphs of segments and $$\\exists {\\mathbb{R}}$$ (2014). arXiv:1406.2636"},{"issue":"1","key":"540_CR34","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1016\/j.jctb.2012.09.004","volume":"103","author":"C McDiarmid","year":"2013","unstructured":"McDiarmid, C., M\u00fcller, T.: Integer realizations of disk and segment graphs. J. Combin. Theory Ser. B 103(1), 114\u2013143 (2013)","journal-title":"J. Combin. Theory Ser. B"},{"key":"540_CR35","unstructured":"Miltzow, T., Schmiermann, R.F.: On classifying continuous constraint satisfaction problems (2021). arXiv:2106.02397"},{"key":"540_CR36","doi-asserted-by":"crossref","unstructured":"Mn\u00ebv, N.E.: The universality theorems on the classification problem of configuration varieties and convex polytopes varieties. In: Topology and Geometry\u2013Rohlin Seminar. Lecture Notes in Mathematics, vol. 1346, pp. 527\u2013543. Springer, Berlin (1988)","DOI":"10.1007\/BFb0082792"},{"key":"540_CR37","volume-title":"Art Gallery Theorems and Algorithms","author":"J O\u2019Rourke","year":"1987","unstructured":"O\u2019Rourke, J.: Art Gallery Theorems and Algorithms. International Series of Monographs on Computer Science. Oxford University Press, New York (1987)"},{"issue":"1","key":"540_CR38","doi-asserted-by":"publisher","first-page":"29","DOI":"10.7155\/jgaa.00548","volume":"25","author":"M Schaefer","year":"2021","unstructured":"Schaefer, M.: Complexity of geometric $$k$$-planarity for fixed $$k$$. J. Graph Algorithms Appl. 25(1), 29\u201341 (2021)","journal-title":"J. Graph Algorithms Appl."},{"issue":"5","key":"540_CR39","doi-asserted-by":"publisher","first-page":"1161","DOI":"10.1007\/s00224-017-9800-y","volume":"62","author":"M Schaefer","year":"2018","unstructured":"Schaefer, M., \u0160tefankovi\u010d, D.: The complexity of tensor rank. Theory Comput. Syst. 62(5), 1161\u20131174 (2018)","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"540_CR40","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."},{"key":"540_CR41","doi-asserted-by":"crossref","unstructured":"Shor, P.W.: Stretchability of pseudolines is NP-hard. In: Applied Geometry and Discrete Mathematics. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol.\u00a04, pp. 531\u2013554. American Mathematical Society, Providence (1991)","DOI":"10.1090\/dimacs\/004\/41"},{"issue":"3","key":"540_CR42","doi-asserted-by":"publisher","first-page":"604","DOI":"10.1090\/S0002-9939-1957-0087106-9","volume":"8","author":"S Smale","year":"1957","unstructured":"Smale, S.: A Vietoris mapping theorem for homotopy. Proc. Am. Math. Soc. 8(3), 604\u2013610 (1957)","journal-title":"Proc. Am. Math. Soc."},{"key":"540_CR43","unstructured":"Stade, J., Tucker-Foltz, J.: Topological universality of the art gallery problem (2022). arXiv:2202.11076"},{"key":"540_CR44","doi-asserted-by":"crossref","unstructured":"Tozoni, D.C., de Rezende, P.J., de Souza, C.C.: Algorithm 966: a practical iterative algorithm for the art gallery problem using integer linear programming. ACM Trans. Math. Softw. 43(2), # 16 (2016)","DOI":"10.1145\/2890491"}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00540-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-023-00540-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00540-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,11]],"date-time":"2024-03-11T15:11:52Z","timestamp":1710169912000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-023-00540-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,27]]},"references-count":44,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,4]]}},"alternative-id":["540"],"URL":"https:\/\/doi.org\/10.1007\/s00454-023-00540-x","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,8,27]]},"assertion":[{"value":"26 January 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 January 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 January 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 August 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}