UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Approximation algorithms for guarding 1.5 dimensional terrains King, James Alexander


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.

Item Media

Item Citations and Data


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.