Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke





.......................

.......................


Publications [#235472] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Bereg, S; Daescu, O; Kaplan, H; Ntafos, S; Zhu, B, Guarding a terrain by two watchtowers, Proceedings of the Annual Symposium on Computational Geometry (2005), pp. 346-355 [doi]
    (last updated on 2017/12/12)

    Abstract:
    Given a polyhedral terrain T with n vertices, the two-watchtower problem for T calls for finding 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. In this paper we present the following results for the two-watchtower problem in ℝ2 and ℝ3: (1) We show that the discrete two-watchtowers problem in ℝ2, where the bases are constrained to lie at vertices of T, can be solved in O(n2 log4 n) time, significantly improving previous solutions. The algorithm works, without increasing its asymptotic running time, even if one of the towers is allowed to be placed anywhere on T. (2) We show that the continuous two-watchtower problem in R2, where the bases can lie anywhere on T, can be solved in O(n 3a(n) log3 n) time, again significantly improving previous results. (3) Still in R2, we show that the continuous version of the problem of guarding a finite set P C T of m points by two watchtowers of smallest height can be solved in O(mn log4 n) time. (4) The discrete version of the two-watchtower problem in ℝ3 can be solved in O(n11/3 polylog(n)) time; this is the first nontrivial result for this problem in ℝ3. Copyright 2005 ACM.

 

dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320