Guarding a 1.5D Terrain with Multiple Imprecise Viewpoints

Given an $n$-vertex 1.5D terrain $\T$ and a set of $m$ edges of $\T$, we study the problem of placing one viewpoint on each edge so that the total length of the visible portions of the terrain is maximized. We present an $O(n+m \log m  )$ time $\frac{1}{2}$-approximation algorithm for the general problem, and polynomial-time algorithms for the cases $m=1$ and $m=2$. Additionally, we show that the problem of computing a point on $\T$ maximizing the visible portion of $\T$ can be solved in $O(n^3)$ time.