Two NP‐Hard Art‐Gallery Problems for Ortho‐Polygons
DOI10.1002/MALQ.19950410212zbMATH Open0827.68115OpenAlexW2115708125MaRDI QIDQ4835529FDOQ4835529
Authors: 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)
Cites Work
Cited In (32)
- Clearing an orthogonal polygon to find the evaders
- On guarding orthogonal polygons with sliding cameras
- How to guard orthogonal polygons: diagonal graphs and vertex covers
- A (7/2)-approximation algorithm for guarding orthogonal art galleries with sliding cameras
- Guarding orthogonal art galleries with sliding cameras
- Approximation algorithms for art gallery problems in polygons
- Approximability of guarding weak visibility polygons
- Optimally guarding 2-reflex orthogonal polyhedra by reflex edge guards
- Art Gallery Problems for Convex Nested Polygons
- Guarding orthogonal art galleries with sliding \(k\)-transmitters: hardness and approximation
- On \(r\)-guarding SCOTs -- a new family of orthogonal polygons
- Computational complexity of the \(r\)-visibility guard set problem for polyominoes
- Vertex guarding for dynamic orthogonal art galleries
- A practical algorithm with performance guarantees for the art gallery problem
- On boundaries of highly visible spaces and applications
- Guarding monotone art galleries with sliding cameras in linear time
- Guarding orthogonal art galleries with sliding cameras
- Constrained light deployment for reducing energy consumption in buildings
- Vertex-to-point conflict-free chromatic guarding is NP-hard
- The parameterized complexity of guarding almost convex polygons
- Polygon exploration with time-discrete vision
- On orthogonally guarding orthogonal polygons with bounded treewidth
- On guarding the vertices of rectilinear domains
- The art gallery theorem for polyominoes
- Topological art in simple galleries
- The dispersive art gallery problem
- Parameterized Analysis of Art Gallery and Terrain Guarding
- Combinatorics and complexity of guarding polygons with edge and point 2-transmitters
- Covering orthogonal polygons with sliding \(k\)-transmitters
- Finding minimum witness sets in orthogonal polygons
- Mobile versus point guards
- An exact algorithm for minimizing vertex guards on art galleries
This page was built for publication: Two NP‐Hard Art‐Gallery Problems for Ortho‐Polygons
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4835529)
