Paper Info
Title
A constant-factor approximation algorithm for optimal terrain guarding
Abstract
We present the first constant-factor approximation algorithm for a non-trivial instance of the optimal guarding (coverage) problem in polygons. In particular, we give an O(1)-approximation algorithm for placing the fewest point guards on a 1.5D terrain, so that every point of the terrain is seen by at least one guard. While polylogarithmic-factor approximations follow from set cover results, our new results exploit geometric structure of terrains to obtain a substantially improved approximation algorithm.
Year
DOI
Venue
2005
10.5555/1070432.1070503
SODA
Keywords
Field
DocType
non-trivial instance,new result,geometric structure,constant-factor approximation algorithm,set cover result,approximation algorithm,optimal terrain,fewest point guard,polylogarithmic-factor approximation,set cover
Discrete mathematics,Set cover problem,Approximation algorithm,Polygon,Combinatorics,Computer science,Terrain,Exploit,Guard (information security)
Conference
ISBN
Citations 
PageRank 
0-89871-585-7
21
1.17
References 
Authors
8
3
Name
Order
Citations
PageRank
Boaz Ben-moshe126227.33
Matthew J. Katz213012.41
Joseph S.B. Mitchell34329428.84