Art Gallery Problem with Rook and Queen Vision
Hannah Alpert, Érika Roldán · Graphs and Combinatorics · 2021
Abstract How many chess rooks or queens does it take to guard all squares of a given polyomino, the union of square tiles from a square grid? This question is a version of the art gallery problem in which the guards can “see” whichever squares the rook or queen attacks. We show that $$\lfloor {\frac{n}{2}} \rfloor $$ ⌊n2⌋ rooks or $$\lfloor {\frac{n}{3}} \rfloor $$ ⌊n3⌋ queens are sufficient and sometimes necessary to guard a polyomino withntiles. We then prove that finding the minimum number of rooks or queens needed to guard a polyomino is NP-hard. These results also apply tod-dimensional rooks and queens ond-dimensional polycubes. Finally, we use bipartite matching theorems to describe sets of non-attacking rooks on polyominoes.