Art gallery problem with rook and queen vision
Authors:
- Hannah AlpertHAHannah Alpert
- Érika RoldánÉRÉrika Roldán
Preprint
Abstract
How many chess rooks or queens does it take to guard all the 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 floor(n/2) rooks or floor(n/3) queens are sufficient and sometimes necessary to guard a polyomino with n tiles. We also prove that finding the minimum number of rooks or the minimum number of queens needed to guard a polyomino is NP-hard. These results also apply to d-dimensional rooks and queens on d-dimensional polycubes. We also use bipartite matching theorems to describe sets of non-attacking rooks on polyominoes.Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- A generalization of Arc-KaylesInternational Journal of Game Theory, 2018
- 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
- POLYGON DECOMPOSITION AND THE ORTHOGONAL ART GALLERY PROBLEMInternational Journal of Computational Geometry & Applications, 2007
- Chessboard Complexes and Matching ComplexesJournal of the London Mathematical Society, 1994
- A unified approach to visibility representations of planar graphsDiscrete & Computational Geometry, 1986
- Computational complexity of art gallery problemsIEEE Transactions on Information Theory, 1986
- Representing a planar graph by vertical lines joining different levelsDiscrete Mathematics, 1983