Back to Search
Start Over
Half-Guarding Weakly-Visible Polygons and Terrains
- Publication Year :
- 2022
- Publisher :
- Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
-
Abstract
- 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).<br />LIPIcs, Vol. 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022), pages 18:1-18:17
Details
- Language :
- English
- Database :
- OpenAIRE
- Accession number :
- edsair.doi...........3cef6ffbadf67428de446d74c872c829
- Full Text :
- https://doi.org/10.4230/lipics.fsttcs.2022.18