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

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

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)

Cited In (9)

• On Guarding Rectilinear Domains
• On the complexity of half-guarding monotone polygons
• Parameter analysis for guarding terrains
• Terrain guarding is NP-hard
• Clique-width of point configurations
• The dispersive art gallery problem
• Parameterized Analysis of Art Gallery and Terrain Guarding
• Title not available (Why is that?)
• Title not available (Why is that?)

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)