A 4-Approximation Algorithm for Guarding 1.5-Dimensional Terrains

DOI10.1007/11682462_58zbMath1145.68596OpenAlexW2169377804MaRDI QIDQ3525796

No author found.

Publication date: 18 September 2008

Published in: LATIN 2006: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11682462_58

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Related Items (15)

Parameterized Analysis of Art Gallery and Terrain Guarding ⋮ One-sided discrete terrain guarding and chordal graphs ⋮ A finite dominating set of cardinality \(O(k)\) and a witness set of cardinality \(O(n)\) for 1.5D terrain guarding problem ⋮ One-sided terrain guarding and chordal graphs ⋮ Guarding 1.5D terrains with demands ⋮ 1.5D terrain guarding problem parameterized by guard range ⋮ On guarding the vertices of rectilinear domains ⋮ Improved approximations for guarding 1.5-dimensional terrains ⋮ Approximation algorithms for art gallery problems in polygons ⋮ Smoothing Imprecise 1.5D Terrains ⋮ Terrain-like graphs: PTASs for guarding weakly-visible polygons and terrains ⋮ Unnamed Item ⋮ Altitude terrain guarding and guarding uni-monotone polygons ⋮ A fixed-parameter algorithm for guarding 1.5D terrains ⋮ Parameter analysis for guarding terrains

This page was built for publication: A 4-Approximation Algorithm for Guarding 1.5-Dimensional Terrains