Exact algorithms for terrain guarding

DOI10.4230/LIPICS.SOCG.2017.11MaRDI QIDQ4580083zbMATH OpenFDO

Authors Pradeesha Ashok, Fedor V. Fomin, Sudeshna Kolay, Saket Saurabh, Meirav Zehavi

Publication date 13 August 2018

zbMATH Keywords

art galleryexponential-time algorithmsterrain guarding

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• Exact algorithms for terrain guarding
• A fixed-parameter algorithm for guarding 1.5D terrains
• 1.5D terrain guarding problem parameterized by guard range
• scientific article; zbMATH DE number 6297811
• scientific article; zbMATH DE number 7236415

Cited in

(11)

• Orthogonal terrain guarding is NP-complete
• Parameter analysis for guarding terrains
• A fixed-parameter algorithm for guarding 1.5D terrains
• The continuous 1.5D terrain guarding problem: discretization, optimal solutions, and PTAS
• Exact algorithms for terrain guarding
• Parameter analysis for guarding terrains
• Terrain guarding is NP-hard
• One-sided terrain guarding and chordal graphs
• scientific article; zbMATH DE number 7236415 (Why is no real title available?)
• 1.5D terrain guarding problem parameterized by guard range
• scientific article; zbMATH DE number 6297811 (Why is no real title available?)

This page was built for publication: Exact algorithms for terrain guarding

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