How to Guard Orthogonal Polygons: Diagonal Graphs and Vertex Covers

详细信息    查看全文

• 作者：T. S. Michael ; Val Pinciu
• 关键词：Art gallery theorem ; Orthogonal polygon ; Vertex cover ; Visibility ; 05C15 ; 05C70 ; 52A37
• 刊名：Discrete and Computational Geometry
• 出版年：2016
• 出版时间：March 2016
• 年：2016
• 卷：55
• 期：2
• 页码：410-422
• 全文大小：598 KB
• 参考文献：1.Aggarwal, A.: The art gallery theorem: its variations, applications and algorithmic aspects. Ph.D. Thesis, Johns Hopkins University, Baltimore (1984)
  2.Cuoto, M.C., de Souza, C.C., de Rezende, P.J.: An exact algorithm for minimizing vertex guards on art galleries. Int. Trans. Oper. Res. 18, 425–448 (2011)CrossRef MathSciNet
  3.Fisk, S.: A short proof of Chvátal’s watchman theorem. J. Comb. Theory Ser. B 24, 374 (1978)CrossRef MathSciNet MATH
  4.Fraughnaugh, K., Locke, S.C.: Finding independent sets in triangle-free graphs. SIAM J. Discrete Math. 9, 674–681 (1996)CrossRef MathSciNet MATH
  5.Ghosh, S.K.: Approximation algorithms for art gallery problems in polygons. Discrete Appl. Math. 158, 718–722 (2010)CrossRef MathSciNet MATH
  6.Hernández-Peñalver, G.: Controlling guards. In: Proceedings of 6th Canadian Conference on Computational Geometry (6CCCG), Waterloo, pp. 387–392 (1994)
  7.Hernández-Peñalver, G.: Vigilancia vigilada de polígonos ortogonales. In: Actes del VI Encuentros de Geometria Computacional, Barcelona, pp. 198–205 (1995)
  8.Hoffmann, F.: On the rectilinear art gallery problem. In: Proceedings of 17th International Colloquium Automata, Languages, and Programming. Lecture Notes in Computer Science, vol. 443, pp. 717–728. Springer, Berlin (1990)
  9.Hoffmann, F., Kriegel, K.: A graph-coloring result and its consequences for polygon-guarding problems. SIAM J. Discrete Math. 9, 210–224 (1996)CrossRef MathSciNet MATH
  10.Katz, M., Roisman, G.: On guarding the vertices of rectilinear domains. Comput. Geom. 39, 219–228 (2008)CrossRef MathSciNet MATH
  11.Kahn, J., Klawe, M., Kleitman, D.: Traditional galleries require fewer watchmen. SIAM J. Algebraic Discrete Methods 4, 194–206 (1983)CrossRef MathSciNet MATH
  12.Kreher, D.L., Radziszowski, S.P.: Minimum triangle-free graphs. Ars Comb. 31, 65–92 (1991)MathSciNet MATH
  13.Lubiw, A.: Decomposing polygons into convex quadrilaterals. In: Proceedings of the 1st ACM Symposium on Computational Geometry, pp. 97–106. ACM Press, New York (1985)
  14.Michael, T.S., Pinciu, V.: Art gallery theorems for guarded guards. Comput. Geom. 26, 247–258 (2003)CrossRef MathSciNet MATH
  15.O’Rourke, J.: An alternate proof of the rectilinear art gallery theorem. J. Geom. 21, 118–130 (1983)CrossRef MathSciNet MATH
  16.O’Rourke, J.: Art Gallery Theorems and Algorithms. Oxford University Press, New York (1987)MATH
  17.Pinciu, V.: Connected guards in orthogonal art galleries. In: Computational Science and Its Applications—ICCSA 2003. Part III. Lecture Notes in Computer Science, vol. 2669, pp. 886–893. Springer, Berlin (2003)
  18.Schuchardt, D., Hecker, H.-D.: Two NP-hard art-gallery problems for ortho-polygons. Math. Log. Q. 41, 261–267 (1995)CrossRef MathSciNet MATH
  19.Shermer, T.C.: Recent results in art gallery theorems. Proc. IEEE 80, 1384–1399 (1992)CrossRef
  20.Zhang, H., He, X.: On even triangulations of 2-connected embedded graphs. SIAM J. Comput. 34, 683–696 (2005)CrossRef MathSciNet MATH
  21.Żyliński, P.: Orthogonal art galleries with holes: a coloring proof of Aggarwal’s theorem. Electron. J. Comb. 13, No. 1, Research paper R20, 10 p. (2006)
  
• 作者单位：T. S. Michael (1)
  Val Pinciu (2)
  
  1. Mathematics Department, United States Naval Academy, Annapolis, MD, 21402, USA
  2. Department of Mathematics, Southern Connecticut State University, New Haven, CT, 06515, USA
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Computational Mathematics and Numerical Analysis
  
• 出版者：Springer New York
• ISSN：1432-0444

文摘

We extend and unify most known results about guarding orthogonal polygons by introducing the same-sign diagonal graphs of a convex quadrangulation and applying results about vertex covers for graphs. Our approach also yields new theorems and often guarantees two disjoint vertex guard sets of relatively small cardinality. For instance, an orthogonal polygon on n vertices has two disjoint vertex guard sets of cardinality at most \(\lfloor n/4\rfloor \). We give new proofs of Aggarwal’s one-hole theorem and the orthogonal fortress theorem. We prove that an orthogonal polygon with n vertices and any number of holes can be protected by at most \(\lfloor (17n-8)/52\rfloor \) vertex guards, improving the best known bound of \(\lfloor n/3\rfloor \). Also, an orthogonal polygon with n vertices and h holes can be protected by \(\lfloor (n+2h)/3\rfloor \) guarded guards, which is best possible when \(n\ge 16h\). Moreover, for orthogonal fortresses with n vertices, \(\lfloor (n+6)/3\rfloor \) guarded guards are always sufficient and sometimes necessary. Keywords Art gallery theorem Orthogonal polygon Vertex cover Visibility