On the complexity of half-guarding monotone polygons
From MaRDI portal
(Redirected from Publication:6164016)
Abstract: We consider a variant of the art gallery problem where all guards are limited to seeing to the right inside a monotone polygon. We call such guards: half-guards. We provide a polynomial-time approximation for point guarding the entire monotone polygon. We improve the best known approximation of 40 from [11], to 8. We also provide an NP-hardness reduction for point guarding a monotone polygon with half-guards.
Cites work
- Allocating vertex \(\pi\)-guards in simple polygons via pseudo-triangulations
- Approximability of guarding weak visibility polygons
- Approximate guarding of monotone and rectilinear polygons
- Art galleries with guards of uniform range of vision
- Computational complexity of art gallery problems
- Guarding galleries and terrains
- scientific article; zbMATH DE number 4065813 (Why is no real title available?)
- scientific article; zbMATH DE number 1424310 (Why is no real title available?)
- Illumination of Orthogonal Polygons with Orthogonal Floodlights
- Illumination of polygons with vertex lights
- Improved approximations for guarding 1.5-dimensional terrains
- On recognizing and characterizing visibility graphs of simple polygons
- Orthogonal terrain guarding is NP-complete
- Terrain guarding is NP-hard
- The Floodlight Problem
- Vertex guarding in weak visibility polygons
Cited in
(2)
This page was built for publication: On the complexity of half-guarding monotone polygons
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6164016)
