A Fast 2-Approximation Algorithm for Guarding Orthogonal Terrains

Yangdi Lyu, Alper Üngör

Terrain Guarding Problem(TGP), which is known to be NP-complete, asks to find a smallest set of guard locations on a terrain $T$ such that every point on $T$ is visible by a guard.…