An Approximation Scheme for Terrain Guarding
DOI10.1007/978-3-642-03685-9_11zbMATH Open1255.68302OpenAlexW1816352825MaRDI QIDQ3638874FDOQ3638874
Authors: Gaurav Kanade, Matt Gibson, Erik Krohn, Kasturi 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
Recommendations
- Guarding terrains via local search
- A constant-factor approximation algorithm for optimal terrain guarding
- A Constant‐Factor Approximation Algorithm for Optimal 1.5D Terrain Guarding
- A 4-Approximation Algorithm for Guarding 1.5-Dimensional Terrains
- Improved approximations for guarding 1.5-dimensional terrains
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Cited In (16)
- Altitude terrain guarding and guarding uni-monotone polygons
- Guarding 1.5D terrains with demands
- A tight analysis of geometric local search
- A fixed-parameter algorithm for guarding 1.5D terrains
- Approximation algorithms for art gallery problems in polygons
- The VC-dimension of visibility on the boundary of monotone polygons
- Parameter analysis for guarding terrains
- On Voronoi visibility maps of 1.5D terrains with multiple viewpoints
- Guarding terrains via local search
- Optimality of geometric local search
- Terrain-like graphs: PTASs for guarding weakly-visible polygons and terrains
- A finite dominating set of cardinality \(O(k)\) and a witness set of cardinality \(O(n)\) for 1.5D terrain guarding problem
- Title not available (Why is that?)
- 1.5D terrain guarding problem parameterized by guard range
- Title not available (Why is that?)
- A constant-factor approximation algorithm for optimal terrain guarding
This page was built for publication: An Approximation Scheme for Terrain Guarding
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3638874)
