Terrain Guarding is NP-Hard
From MaRDI portal
Publication:3115869
DOI10.1137/100791506zbMath1235.68076OpenAlexW2004151341MaRDI QIDQ3115869
No author found.
Publication date: 11 February 2012
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/100791506
Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (21)
The partial visibility curve of the Feigenbaum cascade to chaos ⋮ Guarding monotone art galleries with sliding cameras in linear time ⋮ Parameterized Analysis of Art Gallery and Terrain Guarding ⋮ The VC-dimension of visibility on the boundary of monotone polygons ⋮ Universal Guard Problems ⋮ A finite dominating set of cardinality \(O(k)\) and a witness set of cardinality \(O(n)\) for 1.5D terrain guarding problem ⋮ On orthogonally guarding orthogonal polygons with bounded treewidth ⋮ The dispersive art gallery problem ⋮ On Voronoi visibility maps of 1.5D terrains with multiple viewpoints ⋮ On vertex guarding staircase polygons ⋮ On the complexity of half-guarding monotone polygons ⋮ 1.5D terrain guarding problem parameterized by guard range ⋮ Terrain-like graphs: PTASs for guarding weakly-visible polygons and terrains ⋮ Clique-width of point configurations ⋮ Unnamed Item ⋮ Altitude terrain guarding and guarding uni-monotone polygons ⋮ An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries ⋮ TERRAIN VISIBILITY WITH MULTIPLE VIEWPOINTS ⋮ A fixed-parameter algorithm for guarding 1.5D terrains ⋮ Parameter analysis for guarding terrains ⋮ The complexity of separating points in the plane
This page was built for publication: Terrain Guarding is NP-Hard
