Orthogonal terrain guarding is NP-complete

DOI10.20382/JOCG.V10I2A3zbMATH Open1494.68269OpenAlexW2970343152MaRDI QIDQ5207871FDOQ5207871

Authors Édouard Bonnet, Panos Giannopoulos

Publication date 13 January 2020

Full work available at URL https://jocg.org/index.php/jocg/article/download/3086/2813

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 7236415
• Terrain guarding is NP-hard
• scientific article; zbMATH DE number 6297811
• Exact algorithms for terrain guarding
• Exact algorithms for terrain guarding

Cited in

(9)

• Terrain guarding is NP-hard
• Parameterized Analysis of Art Gallery and Terrain Guarding
• The dispersive art gallery problem
• On the complexity of half-guarding monotone polygons
• scientific article; zbMATH DE number 6297811 (Why is no real title available?)
• Parameter analysis for guarding terrains
• Clique-width of point configurations
• On Guarding Rectilinear Domains
• scientific article; zbMATH DE number 7236415 (Why is no real title available?)

This page was built for publication: Orthogonal terrain guarding is NP-complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5207871)