A Constant‐Factor Approximation Algorithm for Optimal 1.5D Terrain Guarding
From MaRDI portal
Publication:5432364
DOI10.1137/S0097539704446384zbMath1154.68569MaRDI QIDQ5432364
Boaz Ben-Moshe, Joseph S. B. Mitchell, Matthew J. Katz
Publication date: 3 January 2008
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Analysis of algorithms (68W40) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)
Related Items (19)
Parameterized Analysis of Art Gallery and Terrain Guarding ⋮ One-sided discrete terrain guarding and chordal graphs ⋮ A finite dominating set of cardinality \(O(k)\) and a witness set of cardinality \(O(n)\) for 1.5D terrain guarding problem ⋮ On Voronoi visibility maps of 1.5D terrains with multiple viewpoints ⋮ One-sided terrain guarding and chordal graphs ⋮ Guarding 1.5D terrains with demands ⋮ 1.5D terrain guarding problem parameterized by guard range ⋮ Improved approximations for guarding 1.5-dimensional terrains ⋮ Approximation algorithms for art gallery problems in polygons ⋮ SMOOTHING IMPRECISE 1.5D TERRAINS ⋮ The art gallery theorem for polyominoes ⋮ Smoothing Imprecise 1.5D Terrains ⋮ Guarding a terrain by two watchtowers ⋮ Terrain-like graphs: PTASs for guarding weakly-visible polygons and terrains ⋮ Unnamed Item ⋮ Altitude terrain guarding and guarding uni-monotone polygons ⋮ TERRAIN VISIBILITY WITH MULTIPLE VIEWPOINTS ⋮ A fixed-parameter algorithm for guarding 1.5D terrains ⋮ Parameter analysis for guarding terrains
This page was built for publication: A Constant‐Factor Approximation Algorithm for Optimal 1.5D Terrain Guarding
