Exact algorithms for terrain guarding

DOI10.1145/3186897zbMATH Open1454.68153OpenAlexW2799900533WikidataQ129952244 ScholiaQ129952244MaRDI QIDQ4554352FDOQ4554352

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

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

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 (13)

• One-sided discrete terrain guarding and chordal graphs
• Exact algorithms for terrain guarding
• Orthogonal terrain guarding is NP-complete
• A fixed-parameter algorithm for guarding 1.5D terrains
• The continuous 1.5D terrain guarding problem: discretization, optimal solutions, and PTAS
• Parameter analysis for guarding terrains
• Terrain guarding is NP-hard
• Clique-width of point configurations
• One-sided terrain guarding and chordal graphs
• Parameterized Analysis of Art Gallery and Terrain Guarding
• 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 Q4554352)