Improved approximations for guarding 1.5-dimensional terrains

DOI10.1007/s00453-009-9358-4zbMath1215.68272OpenAlexW2164603914MaRDI QIDQ534789

Domagoj Ševerdija, Julián Mestre, Domagoj Matijević, Khaled M. Elbassioni, Erik A. Krohn

Publication date: 10 May 2011

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-009-9358-4

zbMATH Keywords

approximation algorithmsterrain guardinggeometric covering problemstotally balanced matrices

Mathematics Subject Classification ID

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

Related Items (14)

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 ⋮ On the complexity of half-guarding monotone polygons ⋮ One-sided terrain guarding and chordal graphs ⋮ Guarding 1.5D terrains with demands ⋮ 1.5D terrain guarding problem parameterized by guard range ⋮ Terrain-like graphs: PTASs for guarding weakly-visible polygons and terrains ⋮ Unnamed Item ⋮ On Partial Covering For Geometric Set Systems ⋮ Altitude terrain guarding and guarding uni-monotone polygons ⋮ TERRAIN VISIBILITY WITH MULTIPLE VIEWPOINTS ⋮ A fixed-parameter algorithm for guarding 1.5D terrains ⋮ Parameter analysis for guarding terrains

Cites Work

• Unnamed Item
• Rounding to an integral program
• Almost optimal set covers in finite VC-dimension
• An efficient algorithm for determining the convex hull of a finite planar set
• Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem
• A 4-Approximation Algorithm for Guarding 1.5-Dimensional Terrains
• Totally-Balanced and Greedy Matrices
• Improved approximation algorithms for geometric set cover
• Improved Approximations for Guarding 1.5-Dimensional Terrains
• A Constant‐Factor Approximation Algorithm for Optimal 1.5D Terrain Guarding
• Balanced matrices

This page was built for publication: Improved approximations for guarding 1.5-dimensional terrains