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

c 3

x 1

g

c 1

x x

g g g

3 1

x 1

x x

g g g

4 2

x

g g

3

c 2

x

g

1

x

g

2

x

g g g

4

x 2

g

g

c 4

x

g

2

x

g g g

3

x

g g g

x 3

4

g

g

g

g

g g g

x 4

g

g

g

g

Fig. 8. Th e whole polyo mino P tra ns form ed from C = { c 1 , c 2 , c 3 , c 4 } ,where c 1 =
{x 1 ,x 2 , x 3 } , c 2 = {x 1 , x 2 ,x 4 } , c 3 = {x 1 ,x 3 , x 4 } ,and c 4 = {x 2 , x 3 , x 4 } . C is satisfiable
if and only if the whole polyomino is covered by k = 32 cells.

4 Conclusion

In this paper, we studied the art gallery problem when the instance is a poly-
omino with holes. It was shown that locating the minimum number of guards