An Approximation Scheme for Terrain Guarding

DOI10.1007/978-3-642-03685-9_11MaRDI QIDQ3638874zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

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

Cited in

(16)

• A constant-factor approximation algorithm for optimal terrain guarding
• Altitude terrain guarding and guarding uni-monotone polygons
• A tight analysis of geometric local search
• Guarding 1.5D terrains with demands
• Approximation algorithms for art gallery problems in polygons
• A fixed-parameter algorithm for guarding 1.5D terrains
• 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
• scientific article; zbMATH DE number 7236415 (Why is no real title available?)
• 1.5D terrain guarding problem parameterized by guard range
• scientific article; zbMATH DE number 6297811 (Why is no real title available?)

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)