Guarding Terrain using k-Watchtowers

Abstract

The discrete k-watchtower problem for a polyhedral terrain T in R3 with n vertices is to nd k vertical segments, called watchtowers, of smallest height, whose bottom end-points (bases) lie on some vertices of T, and every point of T is visible from the top end-point (tip) of at least one of those watchtowers. In other words, we have to nd k watchtowers whose bottom end-points (bases) lie on some vertices of T, such that every point of T is visible from the tip of at least one watchtower and the maximum height among these k watchtowers is minimized. Zhu [18] gave an algorithm for this problem when k = 1 with running time O(n log n). Agrawal et al. [1] proposed a polynomial time algorithm using parametric search technique for this problem with k = 2. Surprisingly, no result is known for the problem when k > 2. In this thesis, we brie y describe above mentioned algorithmic approaches of Zhu [18] and Agarwal et al [1]. Further, we propose an easy to implement algorithm to solve k-watchtower problem in R3 for a xed constant k. Our algorithm does not use parametric search and it's running time is polynomial in n.