Portal de Periódicos da CAPES

On the Planar Two-Watchtower Problem

2001; Springer Science+Business Media; Linguagem: Inglês

10.1007/3-540-44679-6_14

1611-3349

Sergei Bespamyatnikh, Zhixiang Chen, Kanliang Wang, Binhai Zhu,

Robotic Path Planning Algorithms

In this paper we study the following planar two-watchtower problem: given a terrain (X-monotone chain) T with n vertices, locate two vertical segments (watchtowers) /uv and /u′v′ which have to be erected on T such that every point on T is visible to the top of either watchtowers (u or u′) and the maximum height of /uv, /u′v′ is minimized. We present an O(n 4) time algorithm to solve the discrete version of this problem when v, v′ must be on some vertices of T. Under a mild condition on solving a special cubic equation with three bounded variables in O(f 3) time we can also generalize the algorithm to solve the general problem in O(n 4 +n 3 f 3) time. Using parametric search, the discrete problem can be solvedin O(n 3 log2 n) time and the general problem can be solved in O(n 4 log2 n) time.