Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
Art Gallery Problem with Rook and Queen Vision
View through CrossRef
AbstractHow 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.
Title: Art Gallery Problem with Rook and Queen Vision
Description:
AbstractHow 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.
Related Results
Presentations of Diagram Categories
Presentations of Diagram Categories
We describe the planar rook category, the rook category, the rook-Brauer category, and the Motzkin category in terms of generators and relations. We show that the morphism spaces o...
Rook theory. I. Rook equivalence of Ferrers boards
Rook theory. I. Rook equivalence of Ferrers boards
We introduce a new tool, the factorial polynomials, to study rook equivalence of Ferrers boards. We provide a set of invariants for rook equivalence as well as a very simple algori...
Lists, Spatial Practice and Assistive Technologies for the Blind
Lists, Spatial Practice and Assistive Technologies for the Blind
IntroductionSupermarkets are functionally challenging environments for people with vision impairments. A supermarket is likely to house an average of 45,000 products in a median fl...
Depth-aware salient object segmentation
Depth-aware salient object segmentation
Object segmentation is an important task which is widely employed in many computer vision applications such as object detection, tracking, recognition, and ret...
Vision-specific and psychosocial impacts of low vision among patients with low vision at the eastern regional Low Vision Centre
Vision-specific and psychosocial impacts of low vision among patients with low vision at the eastern regional Low Vision Centre
Purpose: To determine vision-specific and psychosocial implications of low vision among patients with low vision visiting the Low Vision Centre of the Eastern Regional Hospital in ...
A Rook Game
A Rook Game
Problem: Two players take turns moving a rook on an 8×8 chessboard. The rook is only allowed to move south or west (but not both in a single turn), and may move any number of squar...
Analysis of Radix Guitar Marketing Strategy on Queen Guitars Gallery, Bengkulu City
Analysis of Radix Guitar Marketing Strategy on Queen Guitars Gallery, Bengkulu City
In conducting marketing activities a company has several objectives to be achieved, both short-term goals and long-term goals. In the short term it is usually to win the hearts of ...
Steganography Technique Inspired by Rook
Steganography Technique Inspired by Rook
A steganographic technique inspired by rook is presented in this paper to ensure privacy and secrecy. In this approach, the cover image is partitioned into n × 1 pixel blocks and c...