An Approximation Scheme for Terrain Guarding
From MaRDI portal
Publication:3638874
DOI10.1007/978-3-642-03685-9_11zbMath1255.68302OpenAlexW1816352825MaRDI QIDQ3638874
Gaurav Kanade, Erik A. Krohn, Matthew R. Gibson, Kasturi R. Varadarajan
Publication date: 28 October 2009
Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-03685-9_11
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Related Items
The VC-dimension of visibility on the boundary of monotone polygons ⋮ 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 ⋮ Guarding 1.5D terrains with demands ⋮ 1.5D terrain guarding problem parameterized by guard range ⋮ Approximation algorithms for art gallery problems in polygons ⋮ Unnamed Item ⋮ Altitude terrain guarding and guarding uni-monotone polygons ⋮ A fixed-parameter algorithm for guarding 1.5D terrains ⋮ A tight analysis of geometric local search