Open Collections

Approximation algorithms for guarding 1.5 dimensional terrains

University of British Columbia

The 1.5-dimensional terrain guarding problem gives an x-monotone chain (the terrain) and asks for the minimum set of vertices of the terrain (guards) such that every vertex of the terrain is seen by at least one guard. This terrain guarding problem is a restriction of the SET COVER problem, which is known to be both NP-complete and inapproximable within a sub-logarithmic factor [19]. Fortunately, it is known that the 1.5-dimensional terrain guarding problem is approximable to within a constant factor [5, 11], though no attempt has been made to minimize the approximation factor. We give a 4-approximation algorithm for the general 1.5D terrain guarding problem, as well as a 2-approximation algorithm for the case with upwardlooking guards, i.e. when guards cannot see vertices that are below themselves.

Text

2009-12-11

For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.

http://hdl.handle.net/2429/16609

Computer Science

University of British Columbia

UBCV

DSpace