Computational Complexity of the $$r$$-visibility Guard Set Problem for Polyominoes

DOI10.1007/978-3-319-13287-7_8zbMath1452.68247MaRDI QIDQ2945667

Toshihiko Kume, Chuzo Iwamoto

Publication date: 14 September 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-13287-7_8

zbMATH Keywords

NP-hardness; art gallery problem; polyomino; \(r\)-visibility

Mathematics Subject Classification ID

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05B50: Polyominoes

Related Items

On \(r\)-guarding SCOTs -- a new family of orthogonal polygons, Art gallery problem with rook and queen vision

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The art gallery theorem for polyominoes
• Partition into cliques for cubic graphs: Planar case, complexity and approximation
• A combinatorial theorem in plane geometry
• On guarding the vertices of rectilinear domains
• POLYGON DECOMPOSITION AND THE ORTHOGONAL ART GALLERY PROBLEM
• Computational complexity of art gallery problems
• Two NP‐Hard Art‐Gallery Problems for Ortho‐Polygons
• Guarding polyominoes
• Inapproximability results for guarding polygons and terrains