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

art gallery problemcomputational geometryNP-hardnesspolyominovisibility problem

Mathematics Subject Classification ID

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

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

(9)

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

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)