Art Gallery Problem with Rook and Queen Vision
Open Access
- 21 January 2021
- journal article
- research article
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 37 (2) , 621-642
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 $$ rooks or $$\lfloor {\frac{n}{3}} \rfloor $$ 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.
Keywords
All Related Versions
Funding Information
- Division of Mathematical Sciences (DMS 1802914)
- Projekt DEAL
This publication has 24 references indexed in Scilit:
- The Art Gallery Theorem for PolyominoesDiscrete & Computational Geometry, 2012
- A survey of known results and research areas for-queensDiscrete Mathematics, 2009
- Partition into cliques for cubic graphs: Planar case, complexity and approximationDiscrete Applied Mathematics, 2008
- Polyominos and perfect graphsInformation Processing Letters, 1994
- Introduction to AlgorithmsJournal of the Operational Research Society, 1991
- On the queen domination problemDiscrete Mathematics, 1990
- Chessboard domination problemsDiscrete Mathematics, 1990
- On Gallery Watchmen in gridsInformation Processing Letters, 1986
- Representing a planar graph by vertical lines joining different levelsDiscrete Mathematics, 1983
- A combinatorial theorem in plane geometryJournal of Combinatorial Theory, Series B, 1975