Guarding Precise and Imprecise Polyhedral Terrains with Segments

Guarding polyhedral terrains is a fundamental problem with realistic applications. In this paper we study three such problems when the terrains are precise and imprecise respectively. The first problem we consider is to place a segment pq with a fixed length over a precise input terrain T with n vertices in 2D (resp. 3D), such that pq can see every point on T and the maximum y-coordinate (resp. z-coordinate) of p and q is minimized. For terrains in 2D and 3D we present algorithms running in O(n) and \(O(n^3\log n)\) time respectively. The second problem is to place two horizontal segments \(p_1q_1\) and \(p_2q_2\) of a fixed length and with the minimum y-coordinate to cover a 2D terrain (x-monotone chain), which we solve in \(O(n^2\log n)\) time. Given a polyhedral terrain T of n vertices in 3D, a shortest watchtower is a vertical segment erected on T such that every point on T is visible from the top of the segment and the length of the segment is minimized. The problem was solved in \(O(n\log n)\) time more than 30 years ago. In this paper, we investigate the problem under the imprecise model where each vertex of T is on a given vertical interval. We show that when the location of a watchtower is fixed, the problem in 2D and 3D can be solved with linear programming, which leads to an additive \(\varepsilon \) -approximation for the general problem. We implement this algorithm using CPLEX which demonstrate the efficiency and accuracy of the algorithm when \(n\le 100\) .