Math @ Duke

Publications [#235535] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Bereg, S; Daescu, O; Kaplan, H; Ntafos, S; Sharir, M; Zhu, B, Guarding a terrain by two watchtowers,
Algorithmica, vol. 58 no. 2
(2010),
pp. 352390, ISSN 01784617 [doi]
(last updated on 2018/10/18)
Abstract: Given a polyhedral terrain T with n vertices, the twowatchtower 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, semicontinuous, 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 twowatchtower problem in ℝ 2 and ℝ 3: (1) We show that the discrete twowatchtowers problem in ℝ 2 can be solved in O(n 2log∈ 4 n) time, significantly improving previous solutions. The algorithm works, without increasing its asymptotic running time, for the semicontinuous version, where one of the towers is allowed to be placed anywhere on T. (2) We show that the continuous twowatchtower problem in ℝ 2 can be solved in O(n 3 α(n)log∈ 3 n) time, again significantly improving previous results. (3) Still in ℝ 2, we show that the continuous version of the problem of guarding a finite set P⊂T of m points by two watchtowers of smallest common height can be solved in O(mnlog∈ 4 n) time. (4) We show that the discrete version of the twowatchtower problem in ℝ 3 can be solved in O(n 11/3polylog(n)) time; this is the first nontrivial result for this problem in ℝ 3. © 2008 Springer Science+Business Media, LLC.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

