Guarding a terrain by two watchtowers

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 R² and R³: (1) We show that the discrete two-watchtowers problem in R², where the bases are constrained to lie at vertices of T, can be solved in O(n² log⁴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 R², where the bases can lie anywhere on T, can be solved in O(n³α(n)log³n) time, again significantly improving previous results. (3) Still in R², we show that the continuous version of the problem of guarding a finite set P ⊂ T of m points by two watchtowers of smallest height can be solved in O(mn log⁴n) time. (4) The discrete version of the two-watchtower problem in R³ can be solved in O(n^11/3 polylog(n)) time; this is the first nontrivial result for this problem in R³.

REFERENCES

• 1: A. Aggarwal, B. Chazelle, L. Guibas, C. Ó'Dúnlaing and C. Yap, Parallel computational geometry, Algorithmica 3 (1988), 293--328.
• 2: Boaz Ben-Moshe , Paz Carmi , Matthew J. Katz, Computing all large sums-of-pairs in Rⁿ and the discrete planar two-watchtower problem, Information Processing Letters, v.89 n.3, p.137-139, 14 February 2004 [doi>10.1016/j.ipl.2003.07.008]
• 3: Boaz Ben-Moshe , Matthew J. Katz , Joseph S. B. Mitchell, A constant-factor approximation algorithm for optimal terrain guarding, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 4: Sergei Bespamyatnikh , Zhixiang Chen , Kanliang Wang , Binhai Zhu, On the Planar Two-Watchtower Problem, Proceedings of the 7th Annual International Conference on Computing and Combinatorics, p.121-130, August 20-23, 2001
• 5: B. Chazelle , L. J. Guibas, Visibility and intersection problems in plane geometry, Discrete & Computational Geometry, v.4 n.6, p.551-581, Sep. 1989
• 6: Danny Z. Chen , Ovidiu Daescu, Maintaining visibility of a polygon with a moving point of view, Information Processing Letters, v.65 n.5, p.269-275, March 13, 1998 [doi>10.1016/S0020-0190(97)00211-1 ]
• 7: D. Z. Chen, V. Estivvill-Castro and J. Urrutia, Optimal guarding of polygons and monotone chains, Proc. 7th Canadian Conf. on Comput. Geom., 133--138, 1995.
• 8: Kenneth L. Clarkson , Kasturi Varadarajan, Improved approximation algorithms for geometric set cover, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064115]
• 9: Richard Cole, Slowing down sorting networks to obtain faster sorting algorithms, Journal of the ACM (JACM), v.34 n.1, p.200-208, Jan. 1987 [doi>10.1145/7531.7537]
• 10: Richard Cole , Micha Sharir, Visibility problems for polyhedral terrains, Journal of Symbolic Computation, v.7 n.1, p.11-30, Jan. 1989 [doi>10.1016/S0747-7171(89)80003-3]
• 11: D. P. Dobkin and D. G. Kirkpatrick, Fast detection of polyhedral intersection, Theoretical Computer Science 27 (1983), 241--253.
• 12: S. J. Eidenbenz, C. Stamm, and P. Widmayer, Inapproximability results for guarding polygons and terrains. Algorithmica 31 (2001), 79--113
• 13: L. Guibas, J. Hershberger, D. Leven, M. Sharir and R. Tarjan, Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons, Algorithmica 2 (1987), 209--233.
• 14: J. Hershberger, Finding the upper envelope of n line segments in O(n log n) time, Information Processing Letters, v.33 n.4, p.169-174, December 1989 [doi>10.1016/0020-0190(89)90136-1 ]
• 15: J. Matoušek, Range searching with efficient hierarchical cuttings, Discrete Comput. Geom., 10 (1993), 157--182.
• 16: Nimrod Megiddo, Applying Parallel Computation Algorithms in the Design of Serial Algorithms, Journal of the ACM (JACM), v.30 n.4, p.852-865, Oct. 1983 [doi>10.1145/2157.322410]
• 17: M. H. Overmars and J. van Leeuwen, Maintenance of configurations in the plane, J. Comput. System Sci. 23 (1981), 166--204.
• 18: Micha Sharir, The shortest watchtower and related problems for polyhedral terrains, Information Processing Letters, v.29 n.5, p.265-270, November 24, 1988 [doi>10.1016/0020-0190(88)90120-2 ]
• 19: Micha Sharir , Pankaj K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, New York, NY, 1996
• 20: J. Urrutia, Art gallery and illumination problems, in Handbook on Computational Geometry, Elsevier Science Publishers, J.R. Sack and J. Urrutia, eds., pp. 973--1026, 2000.
• 21: Binhai Zhu, Computing the shortest watchtower of a polyhedral terrain in O(nlogn) time, Computational Geometry: Theory and Applications, v.8 n.4, p.181-193, Sept. 1997 [doi>10.1016/S0925-7721(96)00009-0 ]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
art gallery, computational geometry, parametric search, terrain guarding, visibility algorithms