Guarding polyominoes

DOI10.1145/1998196.1998261MaRDI QIDQ5404453zbMATH OpenOpenAlexFDO

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

Publication date 24 March 2014

Published in Proceedings of the twenty-seventh annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1998196.1998261

zbMATH Keywords

computational geometryNP-hardnesspolyominoart gallery problemvisibility problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Polyominoes (05B50)

Recommendations

• The art gallery theorem for polyominoes
• Guarding polyominoes, polycubes and polyhypercubes
• Computational complexity of the \(r\)-visibility guard set problem for polyominoes
• Perfect graphs and guarding rectilinear art galleries
• scientific article; zbMATH DE number 177851

Cited in

(8)

• Computational complexity of the \(r\)-visibility guard set problem for polyominoes
• On \(r\)-guarding SCOTs -- a new family of orthogonal polygons
• Guarding polyominoes, polycubes and polyhypercubes
• The art gallery theorem for polyominoes
• The dispersive art gallery problem
• Combinatorics and complexity of guarding polygons with edge and point 2-transmitters
• Guarding polyominoes under \(k\)-hop visibility
• The guarding game is E-complete

This page was built for publication: Guarding polyominoes

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