Two NP‐Hard Art‐Gallery Problems for Ortho‐Polygons
From MaRDI portal
Publication:4835529
DOI10.1002/malq.19950410212zbMath0827.68115OpenAlexW2115708125MaRDI QIDQ4835529
Dietmar Schuchardt, Hans-Dietrich Hecker
Publication date: 17 December 1995
Published in: Mathematical Logic Quarterly (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/malq.19950410212
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (30)
Guarding monotone art galleries with sliding cameras in linear time ⋮ Parameterized Analysis of Art Gallery and Terrain Guarding ⋮ On boundaries of highly visible spaces and applications ⋮ Vertex-to-point conflict-free chromatic guarding is NP-hard ⋮ Vertex Guarding for Dynamic Orthogonal Art Galleries ⋮ Guarding orthogonal art galleries with sliding cameras ⋮ On orthogonally guarding orthogonal polygons with bounded treewidth ⋮ Optimally guarding 2-reflex orthogonal polyhedra by reflex edge guards ⋮ Computational Complexity of the $$r$$-visibility Guard Set Problem for Polyominoes ⋮ A 3-Approximation Algorithm for Guarding Orthogonal Art Galleries with Sliding Cameras ⋮ The dispersive art gallery problem ⋮ Constrained Light Deployment for Reducing Energy Consumption in Buildings ⋮ On \(r\)-guarding SCOTs -- a new family of orthogonal polygons ⋮ Combinatorics and complexity of guarding polygons with edge and point 2-transmitters ⋮ The parameterized complexity of guarding almost convex polygons ⋮ Topological art in simple galleries ⋮ Finding minimum witness sets in orthogonal polygons ⋮ Clearing an orthogonal polygon to find the evaders ⋮ On Guarding Orthogonal Polygons with Sliding Cameras ⋮ Mobile versus point guards ⋮ GUARDING ORTHOGONAL ART GALLERIES WITH SLIDING CAMERAS ⋮ An exact algorithm for minimizing vertex guards on art galleries ⋮ On guarding the vertices of rectilinear domains ⋮ Guarding orthogonal art galleries with sliding \(k\)-transmitters: hardness and approximation ⋮ Approximation algorithms for art gallery problems in polygons ⋮ The art gallery theorem for polyominoes ⋮ Covering orthogonal polygons with sliding \(k\)-transmitters ⋮ Polygon exploration with time-discrete vision ⋮ How to guard orthogonal polygons: diagonal graphs and vertex covers ⋮ Approximability of guarding weak visibility polygons
Cites Work
This page was built for publication: Two NP‐Hard Art‐Gallery Problems for Ortho‐Polygons
