Inapproximability results for guarding polygons and terrains
From MaRDI portal
Publication:5946124
DOI10.1007/s00453-001-0040-8zbMath0980.68140OpenAlexW2060049097WikidataQ56504466 ScholiaQ56504466MaRDI QIDQ5946124
Stephan J. Eidenbenz, Peter Widmayer, C. Stamm
Publication date: 14 October 2001
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-001-0040-8
Related Items (30)
Parameterized Analysis of Art Gallery and Terrain Guarding ⋮ On boundaries of highly visible spaces and applications ⋮ Multi-agent deployment for visibility coverage in polygonal environments with holes ⋮ Vertex-to-point conflict-free chromatic guarding is NP-hard ⋮ Algorithms for art gallery illumination ⋮ On orthogonally guarding orthogonal polygons with bounded treewidth ⋮ Computational Complexity of the $$r$$-visibility Guard Set Problem for Polyominoes ⋮ Guarding a Polygon Without Losing Touch ⋮ Guarding Art Galleries: The Extra Cost for Sculptures Is Linear ⋮ Observation routes and external watchman routes ⋮ The parameterized complexity of guarding almost convex polygons ⋮ A nearly optimal algorithm for covering the interior of an art gallery ⋮ Topological art in simple galleries ⋮ Improved approximation for guarding simple galleries from the perimeter ⋮ Finding minimum witness sets in orthogonal polygons ⋮ On Guarding Orthogonal Polygons with Sliding Cameras ⋮ A nearly optimal sensor placement algorithm for boundary coverage ⋮ On guarding the vertices of rectilinear domains ⋮ Guarding orthogonal art galleries with sliding \(k\)-transmitters: hardness and approximation ⋮ Approximation algorithms for art gallery problems in polygons ⋮ Finding minimum hidden guard sets in polygons --- tight approximability results ⋮ Illumination in the presence of opaque line segments in the plane ⋮ Guarding a terrain by two watchtowers ⋮ Terrain-like graphs: PTASs for guarding weakly-visible polygons and terrains ⋮ Unnamed Item ⋮ Facets for art gallery problems ⋮ An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries ⋮ How to Keep an Eye on Small Things ⋮ A constant-factor approximation algorithm for vertex guarding a WV-polygon ⋮ Approximability of guarding weak visibility polygons
This page was built for publication: Inapproximability results for guarding polygons and terrains
