Allocating vertex π-guards in simple polygons via pseudo-triangulations

ABSTRACT

We use the concept of pointed pseudo-triangulations to establish new upper and lower bounds on a well known problem from the area of art galleries: What is the worst case optimal number of vertex π-guards that collectively monitor a simple polygon with n vertices?Our results are as follows:1. Any simple polygon with n vertices can be mon- itored by at most [n/2] general vertex π-guards. This bound is tight up to an additive constant of 1.2. Any simple polygon with n vertices, k of which are convex, can be monitored by at most [(2n -- k)/3] edge-aligned vertex π-guards. This is the first non- trivial upper bound for this problem and it is tight for the worst case families of polygons known so far.

REFERENCES

• 1: P. K. Agarwal, J. Basch, L. J. Guibas, J. Hershberger, and L. Zhang, Deformable free space tilings for kinetic collision detection, in: Algorithmic and Computational Robotics: New Directions, Proc. 5th Workshop Algorithmic Found. Robotics (Hanover, NH, 2001), 83--96.
• 2: V. Brumberg, S. Ramaswami, and D. Souvaine, Experimental results on upper bounds for vertex pi-lights, in: Proc. 11th Ann. Fall Workshop on Comput. Geom. (Brooklyn, NY, 2001).
• 3: B. Chazelle, H. Edelsbrunner, M. Gringi, L. J. Guibas, J. Hershberger, M. Sharir, and J. Snoeyink, Ray shooting in polygons using geodesic triangulations, Algorithmica12 (1994), 54--68.
• 4: V. Chvátal, A combinatorial theorem in plane geometry, J. Combin. Theory B18 (1975), 39--41.
• 5: Vladimir Estivill-Castro , Joseph O'Rourke , Jorge Urrutia , Dianna Xu, Illumination of polygons with vertex lights, Information Processing Letters, v.56 n.1, p.9-13, Oct. 13, 1995 [doi>10.1016/0020-0190(95)00129-Z ]
• 6: V. Estivill-Castro and J. Urrutia, Optimal floodlight illumination of orthogonal art galleries, in: Proc. 6th Canadian Conf. Comput. Geom. (Saskatoon, SK, 1994), 81--86.
• 7: S. Fisk, A short proof of Chvátal's watchman theorem, J. Combin. Theory B24 (1978), 374.
• 8: Michael T. Goodrich , Roberto Tamassia, Dynamic ray shooting and shortest paths in planar subdivisions via balanced geodesic triangulations, Journal of Algorithms, v.23 n.1, p.51-73, April 1997 [doi>10.1006/jagm.1995.0797 ]
• 9: D. Kirkpatrick, J. Snoeyink, and B. Speckmann, Kinetic collision detection for simple polygons, Intern. Journal Comp. Geom. Appl.12 (2002), 3--27.
• 10: Michel Pocchiola , Gert Vegter, Pseudo-triangulations: theory and applications, Proceedings of the twelfth annual symposium on Computational geometry, p.291-300, May 24-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237218.237398]
• 11: M. Pocchiola and G. Vegter, Topologically sweeping visibility complexes via pseudo-triangulations, Discrete Comput. Geom.16 (1996), 419--453.
• 12: Joseph O'Rourke, Computational geometry column 43, ACM SIGACT News, v.33 n.1, March 2002 [doi>10.1145/507457.507468]
• 13: Joseph S. B. Mitchell , Joseph O'Rourke, Computational geometry, ACM SIGACT News, v.32 n.3, p.63-72, 09/01/2001 [doi>10.1145/500559.500562]
• 14: J. O'Rourke, Open problems in the combinatorics of visibility and illumination, in: Advances in Discrete and Computational Geometry (B. Chazelle, J. E. Goodman, and R. Pollack, eds.), AMS, Providence, 1998, 237--243.
• 15: J. O'Rourke, Vertex π-lights for monotone mountains, in: Proc. 9th Canadian Conf. Comput. Geom. (Kingston, ON, 1997), 1--5.
• 16: I. Streinu, A combinatorial approach to planar non-colliding robot arm motion planning, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.443, November 12-14, 2000
• 17: Csaba D. Tóth, Art gallery problem with guards whose range of vision is 180°, Computational Geometry: Theory and Applications, v.17 n.3-4, p.121-134, Dec. 2000 [doi>10.1016/S0925-7721(00)00023-7 ]
• 18: Csaba D. Tóth, Illuminating Polygons with Vertex pi-Floodlights, Proceedings of the International Conference on Computational Sciences-Part I, p.772-784, May 28-30, 2001
• 19: G. T. Toussaint, Computing geodesic properties inside a simple polygon, Revue D'Intelligence Artificielle3 (1989), 9--42.
• 20: J. Urrutia, Art Gallery and Illumination Problems, in: Handbook on Computational Geometry (J. R. Sack, J. Urrutia, eds.), Elsevier, Amsterdam, 2000, 973--1027.
• 21: J. Urrutia, personal communication, 2001.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Theory