1.5D terrain guarding problem parameterized by guard range

DOI10.1016/j.tcs.2016.11.015zbMath1356.68088OpenAlexW2549601059MaRDI QIDQ501659

Farnoosh Khodakarami, Ali Mohades, Farzad Didehvar

Publication date: 9 January 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2016.11.015

zbMATH Keywords

dynamic programmingparameterized complexityguarding1.5D terrain

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Improved approximations for guarding 1.5-dimensional terrains
• Improved approximation algorithms for geometric set cover
• A fixed-parameter algorithm for guarding 1.5D terrains
• Parametrized complexity theory.
• Reflections on Multivariate Algorithmics and Problem Parameterization
• Terrain Guarding is NP-Hard
• A 4-Approximation Algorithm for Guarding 1.5-Dimensional Terrains
• An Approximation Scheme for Terrain Guarding
• A Constant‐Factor Approximation Algorithm for Optimal 1.5D Terrain Guarding
• Visibility Algorithms in the Plane
• Parameterized Algorithms

This page was built for publication: 1.5D terrain guarding problem parameterized by guard range