Computational Complexity of the r-visibility Guard Set Problem for Polyominoes - Discrete and Computational Geometry and Graphs - page 95

with -visibility in a polyomino with holes is NP-hard. As a corollary, the same

problem for orthogonal polygons with holes is NP-hard.

r

References

1. Biedl, T., Irfan, M.T., Iwerks, J., Kim, J., Mitchell, J.S.B.: Guarding polyominoes.
In: 27th Annual Symposium on Computational Geometry, pp. 387-396 (2011)
2. Biedl, T., Irfan, M.T., Iwerks, J., Kim, J., Mitchell, J.S.B.: The art gallery theorem
for polyominoes. Discrete Comput. Geom. 48 (3), 711-720 (2012)
3. Cerioli, M.R., Faria, L., Ferreira, T.O., Martinhon, C.A.J., Protti, F., Reed, B.:
Partition into cliques for cubic graphs: Planar case, complexity and approximation.
Discrete Appl. Math. 156 (12), 2270-2278 (2008)
4. Chvatal, V.: A combinatorial theorem in plane geometry. J. Comb. Theory B. 18 ,
39-41 (1975)
5. Eidenbenz, S.J., Stamm, C., Widmayer, P.: Inapproximability results for guarding
polygons and terrains. Algorithmica 31 , 79-113 (2001)
6. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory
of NP-Completeness. W.H. Freeman, New York (1979)
7. Hoffman, F.: On the rectilinear art gallery problem. In: Paterson, M. (ed.) ICALP
1990. LNCS, vol. 443, pp. 717-728. Springer, Heidelberg (1990)
8. Katz, M.J., Roisman, G.S.: On guarding the vertices of rectilinear domains. Comp.
Geom. Theor. Appl. 39 (3), 219-228 (2008)
9. Lee, D.T., Lin, A.K.: Computational complexity of art gallery problems. IEEE
Trans. Inform. Theory 32 (2), 276-282 (1986)
10. O'Rourke, J.: Art Gallery Theorems and Algorithms. Oxford University Press,
New York (1987)
11. Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Mass (1994)
12. Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction.
Springer, New York (1985)
13. Schuchardt, D., Hecker, H.-D.: Two NP-hard art-gallery problems for ortho-
polygons. Math. Logic Quar. 41 (2), 261-267 (1995)
14. Worman, C., Keil, J.M.: Polygon decomposition and the orthogonal art gallery
problem. Int. J. Comput. Geom. Ap. 17 (2), 105-138 (2007)