{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T02:33:18Z","timestamp":1771036398288,"version":"3.50.1"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2025,1,11]],"date-time":"2025-01-11T00:00:00Z","timestamp":1736553600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,1,11]],"date-time":"2025-01-11T00:00:00Z","timestamp":1736553600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004359","name":"Vetensk\u00e5psradet","doi-asserted-by":"publisher","award":["2021-03810"],"award-info":[{"award-number":["2021-03810"]}],"id":[{"id":"10.13039\/501100004359","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001858","name":"VINNOVA","doi-asserted-by":"publisher","award":["2018-04101"],"award-info":[{"award-number":["2018-04101"]}],"id":[{"id":"10.13039\/501100001858","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003945","name":"Link\u00f6ping University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100003945","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2025,4]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>We study the <jats:sc>Art Gallery Problem<\/jats:sc> under <jats:italic>k<\/jats:italic>-hop visibility in polyominoes. In this visibility model, two unit squares of a polyomino can see each other if and only if the shortest path between the respective vertices in the dual graph of the polyomino has length at most\u00a0<jats:italic>k<\/jats:italic>. In this paper, we show that the VC dimension of this problem is 3 in simple polyominoes, and 4 in polyominoes with holes. Furthermore, we provide a reduction from <jats:sc>Planar Monotone 3Sat<\/jats:sc>, thereby showing that the problem is -complete even in thin polyominoes (i.e., polyominoes that do not a contain a <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$2\\times 2$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>2<\/mml:mn>\n                    <mml:mo>\u00d7<\/mml:mo>\n                    <mml:mn>2<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> block of cells). Complementarily, we present a linear-time 4-approximation algorithm for simple 2-thin polyominoes (which do not contain a <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$3\\times 3$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>3<\/mml:mn>\n                    <mml:mo>\u00d7<\/mml:mo>\n                    <mml:mn>3<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> block of cells) for all <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$k\\in {\\mathbb {N}}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>\u2208<\/mml:mo>\n                    <mml:mi>N<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s00453-024-01292-7","type":"journal-article","created":{"date-parts":[[2025,1,11]],"date-time":"2025-01-11T10:46:51Z","timestamp":1736592411000},"page":"572-593","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Guarding Polyominoes Under k-Hop Visibility"],"prefix":"10.1007","volume":"87","author":[{"given":"Omrit","family":"Filtser","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erik","family":"Krohn","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bengt\u00a0J.","family":"Nilsson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Rieck","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christiane","family":"Schmidt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,1,11]]},"reference":[{"key":"1292_CR1","doi-asserted-by":"crossref","unstructured":"Abrahamsen, Mikkel, Adamaszek, Anna, Miltzow, Tillmann: The art gallery problem is \u2203$${\\mathbb{R}}$$- complete. J. ACM 69(1), 4:1\u20134:70 (2022). https:\/\/doi.org\/10.1145\/3486220","DOI":"10.1145\/3486220"},{"key":"1292_CR2","doi-asserted-by":"publisher","first-page":"488","DOI":"10.1016\/j.dam.2022.06.006","volume":"320","author":"A Karim Abu-Affash","year":"2022","unstructured":"Karim Abu-Affash, A., Carmi, P., Krasin, A.: A linear-time algorithm for minimum $$k$$-hop dominating set of a cactus graph. Discret. Appl. Math. 320, 488\u2013499 (2022). https:\/\/doi.org\/10.1016\/j.dam.2022.06.006","journal-title":"Discret. Appl. Math."},{"key":"1292_CR3","doi-asserted-by":"publisher","unstructured":"Amis, A.D., Prakash, R., Huynh, D.T., Vuong, T.H.P.: Max\u2013min $$d$$-cluster formation in wireless ad hoc networks. In: Conference on Computer Communications, pp. 32\u201341 (2000). https:\/\/doi.org\/10.1109\/INFCOM.2000.832171","DOI":"10.1109\/INFCOM.2000.832171"},{"key":"1292_CR4","doi-asserted-by":"publisher","first-page":"101687","DOI":"10.1016\/j.comgeo.2020.101687","volume":"92","author":"B Aronov","year":"2021","unstructured":"Aronov, B., Donakonda, A., Ezra, E., Pinchasi, R.: On pseudo-disk hypergraphs. Comput. Geom. 92, 101687 (2021). https:\/\/doi.org\/10.1016\/j.comgeo.2020.101687","journal-title":"Comput. Geom."},{"key":"1292_CR5","doi-asserted-by":"publisher","unstructured":"Basuchowdhuri, P., Majumder, S.: Finding influential nodes in social networks using minimum $$k$$-hop dominating set. In: International Conference on Applied Algorithms (ICAA), pp. 137\u2013151 (2014). https:\/\/doi.org\/10.1007\/978-3-319-04126-1_12","DOI":"10.1007\/978-3-319-04126-1_12"},{"key":"1292_CR6","doi-asserted-by":"publisher","unstructured":"Biedl, T.C., Irfan, M.T., Iwerks, J., Kim, J., Mitchell, J.S.B.: Guarding polyominoes. In: Symposium on Computational Geometry, pp. 387\u2013396 (2011). https:\/\/doi.org\/10.1145\/1998196.1998261","DOI":"10.1145\/1998196.1998261"},{"issue":"3","key":"1292_CR7","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0925-7721(97)00026-6","volume":"9","author":"TC Biedl","year":"1998","unstructured":"Biedl, T.C., Kant, G.: A better heuristic for orthogonal graph drawings. Comput. Geom. 9(3), 159\u2013180 (1998). https:\/\/doi.org\/10.1016\/S0925-7721(97)00026-6","journal-title":"Comput. Geom."},{"key":"1292_CR8","doi-asserted-by":"publisher","unstructured":"Biedl, T.C., Mehrabi, S.: On $$r$$-guarding thin orthogonal polygons. In: International Symposium on Algorithms and Computation (ISAAC), pp. 17:1\u201317:13 (2016). https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2016.17","DOI":"10.4230\/LIPIcs.ISAAC.2016.17"},{"issue":"2","key":"1292_CR9","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1007\/s00453-020-00769-5","volume":"83","author":"TC Biedl","year":"2021","unstructured":"Biedl, T.C., Mehrabi, S.: On orthogonally guarding orthogonal polygons with bounded treewidth. Algorithmica 83(2), 641\u2013666 (2021). https:\/\/doi.org\/10.1007\/s00453-020-00769-5","journal-title":"Algorithmica"},{"key":"1292_CR10","doi-asserted-by":"publisher","unstructured":"Borradaile, G., Le, H.: Optimal dynamic program for $$r$$-domination problems over tree decompositions. In: International Symposium on Parameterized and Exact Computation (IPEC), pp. 8:1\u20138:23 (2017). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2016.8","DOI":"10.4230\/LIPIcs.IPEC.2016.8"},{"issue":"4","key":"1292_CR11","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. Discret. Comput. Geom. 14(4), 463\u2013479 (1995). https:\/\/doi.org\/10.1007\/BF02570718","journal-title":"Discret. Comput. Geom."},{"issue":"03","key":"1292_CR12","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1142\/S0218195912500045","volume":"22","author":"M de Berg","year":"2012","unstructured":"de Berg, M., Khosravi, A.: Optimal binary space partitions for segments in the plane. Int. J. Comput. Geom. Appl. 22(03), 187\u2013205 (2012). https:\/\/doi.org\/10.1142\/S0218195912500045","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"1","key":"1292_CR13","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1145\/1077464.1077468","volume":"1","author":"ED Demaine","year":"2005","unstructured":"Demaine, E.D., Fomin, F.V., Hajiaghayi, M.T., Thilikos, D.M.: Fixed-parameter algorithms for ($$k, r$$)-center in planar graphs and map graphs. ACM Trans. Algorithms 1(1), 33\u201347 (2005). https:\/\/doi.org\/10.1145\/1077464.1077468","journal-title":"ACM Trans. Algorithms"},{"key":"1292_CR14","doi-asserted-by":"publisher","unstructured":"Filtser, A., Le, H.: Clan embeddings into trees, and low treewidth graphs. In: Symposium on Theory of Computing, pp. 342\u2013355 (2021). https:\/\/doi.org\/10.1145\/3406325.3451043","DOI":"10.1145\/3406325.3451043"},{"key":"1292_CR15","doi-asserted-by":"publisher","unstructured":"Filtser, A., Le, H.: Low treewidth embeddings of planar and minor-free metrics. In: Symposium on Foundations of Computer Science (FOCS), pp. 1081\u20131092 (2022). https:\/\/doi.org\/10.1109\/FOCS54457.2022.00105","DOI":"10.1109\/FOCS54457.2022.00105"},{"key":"1292_CR16","doi-asserted-by":"publisher","unstructured":"Filtser, O., Krohn, E., Nilsson, B.J., Rieck, C., Schmidt, C.: Guarding polyominoes under $$k$$-hop visibility. In: Latin American Symposium on Theoretical Informatics (LATIN), pp. 288\u2013302 (2024). https:\/\/doi.org\/10.1007\/978-3-031-55598-5_19","DOI":"10.1007\/978-3-031-55598-5_19"},{"key":"1292_CR17","doi-asserted-by":"publisher","unstructured":"Fox-Epstein, E., Klein, P.N., Schild, A.: Embedding planar graphs into low-treewidth graphs with applications to efficient approximation schemes for metric problems. In: Symposium on Discrete Algorithms (SODA), pp. 1069\u20131088 (2019). https:\/\/doi.org\/10.1137\/1.9781611975482.66","DOI":"10.1137\/1.9781611975482.66"},{"key":"1292_CR18","doi-asserted-by":"publisher","unstructured":"Gibson, M., Krohn, E., Wang, Q.: The VC-dimension of visibility on the boundary of a simple polygon. In: International Symposium on Algorithms and Computation (ISAAC), pp. 541\u2013551 (2015). https:\/\/doi.org\/10.1007\/978-3-662-48971-0_46","DOI":"10.1007\/978-3-662-48971-0_46"},{"issue":"1","key":"1292_CR19","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). https:\/\/doi.org\/10.1016\/j.comgeo.2013.08.012","journal-title":"Comput. Geom."},{"issue":"2","key":"1292_CR20","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D Haussler","year":"1987","unstructured":"Haussler, D., Welzl, E.: $$\\varepsilon $$-nets and simplex range queries. Discret. Comput. Geom. 2(2), 127\u2013151 (1987). https:\/\/doi.org\/10.1007\/BF02187876","journal-title":"Discret. Comput. Geom."},{"key":"1292_CR21","doi-asserted-by":"publisher","unstructured":"Iwamoto, C., Kume, T.: Computational complexity of the $$r$$-visibility guard set problem for polyominoes. In: Japanese Conference on Discrete and Computational Geometry and Graphs (JCDCGG), pp. 87\u201395 (2013). https:\/\/doi.org\/10.1007\/978-3-319-13287-7_8","DOI":"10.1007\/978-3-319-13287-7_8"},{"key":"1292_CR22","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1016\/j.dam.2018.11.002","volume":"264","author":"I Katsikarelis","year":"2019","unstructured":"Katsikarelis, I., Lampis, M., Paschos, V.T.: Structural parameters, tight bounds, and approximation for ($$k, r$$)-center. Discret. Appl. Math. 264, 90\u2013117 (2019). https:\/\/doi.org\/10.1016\/j.dam.2018.11.002","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"1292_CR23","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/j.ipl.2015.07.014","volume":"116","author":"S Kundu","year":"2016","unstructured":"Kundu, S., Majumder, S.: A linear time algorithm for optimal $$k$$-hop dominating set of a tree. Inf. Process. Lett. 116(2), 197\u2013202 (2016). https:\/\/doi.org\/10.1016\/j.ipl.2015.07.014","journal-title":"Inf. Process. Lett."},{"key":"1292_CR24","unstructured":"Langetepe, E., Lehmann, S.: Exact VC-dimension for $$L_1$$-visibility of points in simple polygons, (2017). https:\/\/doi.org\/10.48550\/arXiv.1705.01723"},{"issue":"2","key":"1292_CR25","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1109\/TIT.1986.1057165","volume":"32","author":"D-T Lee","year":"1986","unstructured":"Lee, D.-T., Lin, A.K.: Computational complexity of art gallery problems. IEEE Trans. Inf. Theory 32(2), 276\u2013282 (1986). https:\/\/doi.org\/10.1109\/TIT.1986.1057165","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1","key":"1292_CR26","doi-asserted-by":"publisher","first-page":"225","DOI":"10.2140\/pjm.1975.61.225","volume":"61","author":"A Meir","year":"1975","unstructured":"Meir, A., Moon, J.W.: Relations between packing and covering numbers of a tree. Pac. J. Math. 61(1), 225\u2013233 (1975). https:\/\/doi.org\/10.2140\/pjm.1975.61.225","journal-title":"Pac. J. Math."},{"issue":"2","key":"1292_CR27","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.: Some NP-hard polygon decomposition problems. IEEE Trans. Inf. Theory 29(2), 181\u2013190 (1983). https:\/\/doi.org\/10.1109\/TIT.1983.1056648","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1292_CR28","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/j.endm.2015.06.024","volume":"49","author":"V Pinciu","year":"2015","unstructured":"Pinciu, V.: Guarding polyominoes, polycubes and polyhypercubes. Electron. Notes Discret. Math. 49, 159\u2013166 (2015). https:\/\/doi.org\/10.1016\/j.endm.2015.06.024","journal-title":"Electron. Notes Discret. Math."},{"key":"1292_CR29","doi-asserted-by":"publisher","unstructured":"Tom\u00e1s, A.P.: Guarding thin orthogonal polygons is hard. In: Fundamentals of Computation Theory (FCT), pp. 305\u2013316 (2013). https:\/\/doi.org\/10.1007\/978-3-642-40164-0_29","DOI":"10.1007\/978-3-642-40164-0_29"},{"issue":"1","key":"1292_CR30","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. Israel J. Math. 104(1), 1\u201316 (1998). https:\/\/doi.org\/10.1007\/BF02897056","journal-title":"Israel J. Math."},{"issue":"2","key":"1292_CR31","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1137\/1116025","volume":"16","author":"VN Vapnik","year":"1971","unstructured":"Vapnik, V.N., Chervonenkis, A.Y.: On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl. 16(2), 264\u2013280 (1971). https:\/\/doi.org\/10.1137\/1116025","journal-title":"Theory Probab. Appl."},{"issue":"2","key":"1292_CR32","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1142\/S0218195907002264","volume":"17","author":"C Worman","year":"2007","unstructured":"Worman, C., Mark Keil, J.: Polygon decomposition and the orthogonal art gallery problem. Int. J. Comput. Geom. Appl. 17(2), 105\u2013138 (2007). https:\/\/doi.org\/10.1142\/S0218195907002264","journal-title":"Int. J. Comput. Geom. Appl."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01292-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-024-01292-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01292-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,23]],"date-time":"2025-03-23T05:23:35Z","timestamp":1742707415000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-024-01292-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,11]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,4]]}},"alternative-id":["1292"],"URL":"https:\/\/doi.org\/10.1007\/s00453-024-01292-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,11]]},"assertion":[{"value":"9 May 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 December 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 January 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}