Two NP‐Hard Art‐Gallery Problems for Ortho‐Polygons

DOI10.1002/MALQ.19950410212MaRDI QIDQ4835529zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

visibilityart-gallery problemscomplexity of geometric problems

Mathematics Subject Classification ID

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

• scientific article; zbMATH DE number 4065813 (Why is no real title available?)
• Computational complexity of art gallery problems

Cited in

(31)

• On \(r\)-guarding SCOTs -- a new family of orthogonal polygons
• Approximation algorithms for art gallery problems in polygons
• Computational complexity of the \(r\)-visibility guard set problem for polyominoes
• Parameterized Analysis of Art Gallery and Terrain Guarding
• Clearing an orthogonal polygon to find the evaders
• Guarding orthogonal art galleries with sliding cameras
• On orthogonally guarding orthogonal polygons with bounded treewidth
• Guarding orthogonal art galleries with sliding cameras
• The dispersive art gallery problem
• Vertex guarding for dynamic orthogonal art galleries
• Topological art in simple galleries
• Approximability of guarding weak visibility polygons
• Constrained light deployment for reducing energy consumption in buildings
• On boundaries of highly visible spaces and applications
• Finding minimum witness sets in orthogonal polygons
• Vertex-to-point conflict-free chromatic guarding is NP-hard
• Art Gallery Problems for Convex Nested Polygons
• Optimally guarding 2-reflex orthogonal polyhedra by reflex edge guards
• Mobile versus point guards
• The art gallery theorem for polyominoes
• On guarding the vertices of rectilinear domains
• Combinatorics and complexity of guarding polygons with edge and point 2-transmitters
• A practical algorithm with performance guarantees for the art gallery problem
• On guarding orthogonal polygons with sliding cameras
• Polygon exploration with time-discrete vision
• An exact algorithm for minimizing vertex guards on art galleries
• How to guard orthogonal polygons: diagonal graphs and vertex covers
• Covering orthogonal polygons with sliding \(k\)-transmitters
• Guarding orthogonal art galleries with sliding \(k\)-transmitters: hardness and approximation
• Guarding monotone art galleries with sliding cameras in linear time
• The parameterized complexity of guarding almost convex polygons

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)