The art gallery theorem for polyominoes

DOI10.1007/S00454-012-9429-1zbMATH Open1251.05029OpenAlexW2016780725MaRDI QIDQ715003FDOQ715003

Authors: Mohammad T. Irfan, Justin Iwerks, Joondong Kim, Joseph S. B. Mitchell, Therese Biedl 

Publication date: 15 October 2012

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-012-9429-1

Recommendations

• Guarding polyominoes
• Guarding polyominoes, polycubes and polyhypercubes
• scientific article; zbMATH DE number 177851
• scientific article; zbMATH DE number 1424310
• Perfect graphs and guarding rectilinear art galleries

zbMATH Keywords

art gallery theorempolyominoguard numbervisibility coverage

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Polyominoes (05B50)

Cites Work

• On guarding the vertices of rectilinear domains
• Traditional Galleries Require Fewer Watchmen
• Title not available (Why is that?)
• Title not available (Why is that?)
• Two NP‐Hard Art‐Gallery Problems for Ortho‐Polygons
• An alternative proof of the rectilinear art gallery theorem
• Approximation algorithms for art gallery problems in polygons
• Title not available (Why is that?)
• An efficient algorithm for guard placement in polygons with holes
• A Short Proof of the Rectilinear Art Gallery Theorem
• Automata, Languages and Programming
• Guarding galleries and terrains
• Guarding polyominoes
• Locating guards for visibility coverage of polygons
• POLYGON DECOMPOSITION AND THE ORTHOGONAL ART GALLERY PROBLEM
• A Constant‐Factor Approximation Algorithm for Optimal 1.5D Terrain Guarding
• Computational complexity of art gallery problems

Cited In (16)

• The Martin Gardner Polytopes
• Art Gallery Problems for Convex Nested Polygons
• On \(r\)-guarding SCOTs -- a new family of orthogonal polygons
• Art gallery problem with rook and queen vision
• Computational complexity of the \(r\)-visibility guard set problem for polyominoes
• Title not available (Why is that?)
• Guarding monotone art galleries with sliding cameras in linear time
• Guarding orthogonal art galleries with sliding cameras
• The art gallery theorem for simple polygons in terms of the number of reflex and convex vertices
• Guarding polyominoes, polycubes and polyhypercubes
• On orthogonally guarding orthogonal polygons with bounded treewidth
• The dispersive art gallery problem
• The smallest art gallery not guarded by every third vertex
• Ortho-unit polygons can be guarded with at most \(\left\lfloor \frac{n-4}{8} \right\rfloor\) guards
• Perfect graphs and guarding rectilinear art galleries
• Guarding polyominoes

This page was built for publication: The art gallery theorem for polyominoes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q715003)