A Fast 2-Approximation Algorithm for Guarding Orthogonal Terrains

2016/05/11 by Lyu, Yangdi, Üngör, Alper
#Computational Geometry (cs.CG) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1605.03271

Abstract

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. Here, we study this problem on 1.5D orthogonal terrains where the edges are bound to be horizontal or vertical. We propose a 2-approximation algorithm that runs in O(n log m) time, where n and m are the sizes of input and output, respectively. This is an improvement over the previous best algorithm, which is a 2-approximation with O(n²) running time.

Related

• A Linear-Time Approximation Algorithm for the Orthogonal Terrain Guarding Problem
• Improved Approximations for Guarding 1.5-Dimensional Terrains
• The continuous 1.5D terrain guarding problem: Discretization, optimal solutions, and PTAS
• A PTAS for the continuous 1.5D Terrain Guarding Problem
• Orthogonal Terrain Guarding is NP-complete