Guarding a Terrain by Two Watchtowersby Pankaj K. Agarwal, Sergey Bereg, Ovidiu Daescu, Haim Kaplan, Simeon Ntafos, Micha Sharir and Binhai Zhu
Figure 1: The three versions of the problem in R3: discrete, semi-continuous, and continuous. Abstract: Given a polyhedral terrain T with n vertices, the two-watchtower problem for T asks to find two vertical segments, called watchtowers, of smallest common height, whose bottom endpoints (bases) lie on T, and whose top endpoints guard T, in the sense that each point on T is visible from at least one of them. There are three versions of the problem, discrete, semi-continuous, and continuous, depending on whether two, one, or none of the two bases are restricted to be among the vertices of T, respectively.
In this paper we present the following results for the two-watchtower
problem in R2 and R3: Keywords: Computational geometry - Visibility algorithms - Terrain guarding - Parametric search @article{bbbgz-vdpc-10 , author = {Pankaj Agarwal and Sergey Bereg and Ovidiu Daescu and Haim Kaplan and Simeon Ntafos and Micha Sharir and Binhai Zhu} , title = {Guarding a Terrain by Two Watchtowers} , journal = {Algorithmica} , year = {2010} , volume = {58} , number = {2} , pages = {352--390} , url = {http://dx.doi.org/10.1007/s00453-008-9270-3} } |