Exact algorithms for terrain guarding

DOI10.1145/3186897MaRDI QIDQ4554352zbMATH OpenOpenAlexWikidataFDO

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

Publication date 13 November 2018

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://research.tue.nl/nl/publications/58bcab69-eace-4999-9cf6-8c5af8462c3c

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 7236415
• scientific article; zbMATH DE number 6297811

Cited in

(14)

• Terrain guarding is NP-hard
• The continuous 1.5D terrain guarding problem: discretization, optimal solutions, and PTAS
• One-sided discrete terrain guarding and chordal graphs
• Parameterized Analysis of Art Gallery and Terrain Guarding
• Parameter analysis for guarding terrains
• One-sided terrain guarding and chordal graphs
• Exact algorithms for terrain guarding
• Orthogonal terrain guarding is NP-complete
• scientific article; zbMATH DE number 6297811 (Why is no real title available?)
• 1.5D terrain guarding problem parameterized by guard range
• A fixed-parameter algorithm for guarding 1.5D terrains
• Parameter analysis for guarding terrains
• Clique-width of point configurations
• scientific article; zbMATH DE number 7236415 (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 Q4554352)