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

DOI10.1007/978-3-319-13287-7_8zbMath1452.68247OpenAlexW196654191MaRDI 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-hardnessart gallery problempolyomino\(r\)-visibility

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Polyominoes (05B50)

Related Items (2)

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

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Computational Complexity of the $$r$$-visibility Guard Set Problem for Polyominoes