2026-07-26T12:07:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17410 2024-03-06T10:59:41Z ddc:004 open_access

Half-Guarding Weakly-Visible Polygons and Terrains Duraisamy, Nandhana Hillberg, Hannah Miller Jallu, Ramesh K. Krohn, Erik Maheshwari, Anil Nandy, Subhas C. Pahlow, Alex Art Gallery Problem Approximation Algorithm NP-Hardness Monotone Polygons Half-Guards We consider a variant of the art gallery problem where all guards are limited to seeing 180degree. Guards that can only see in one direction are called half-guards. We give a polynomial time approximation scheme for vertex guarding the vertices of a weakly-visible polygon with half-guards. We extend this to vertex guarding the boundary of a weakly-visible polygon with half-guards. We also show NP-hardness for vertex guarding a weakly-visible polygon with half-guards. Lastly, we show that the orientation of half-guards is critical in terrain guarding. Depending on the orientation of the half-guards, the problem is either very easy (polynomial time solvable) or very hard (NP-hard). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nandhana Duraisamy and Hannah Miller Hillberg and Ramesh K. Jallu and Erik Krohn and Anil Maheshwari and Subhas C. Nandy and Alex Pahlow 2022 Is Part Of LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2022.18 urn:nbn:de:0030-drops-174103 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.18 eng https://creativecommons.org/licenses/by/4.0/legalcode