Exact algorithms for terrain guarding

DOI10.4230/LIPICS.SOCG.2017.11zbMATH Open1433.68478MaRDI QIDQ4580083FDOQ4580083

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

Publication date: 13 August 2018

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

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)

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
• Title not available (Why is that?)
• 1.5D terrain guarding problem parameterized by guard range
• Title not available (Why is that?)

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)