Guarding 1.5D terrains with demands

DOI10.1080/00207160.2012.707800zbMath1255.90076OpenAlexW2030193964MaRDI QIDQ4902836

Domagoj Matijević, Domagoj Ševerdija, Khaled M. Elbassioni

Publication date: 18 January 2013

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/00207160.2012.707800

zbMATH Keywords

approximation algorithmtotally balanced matricesLP relaxation1.5D terrain guardingdemands

Mathematics Subject Classification ID

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

Related Items (1)

A finite dominating set of cardinality \(O(k)\) and a witness set of cardinality \(O(n)\) for 1.5D terrain guarding problem

Cites Work

• Unnamed Item
• Improved approximations for guarding 1.5-dimensional terrains
• Improved approximation algorithms for geometric set cover
• On the set multicover problem in geometric settings
• A 4-Approximation Algorithm for Guarding 1.5-Dimensional Terrains
• An Approximation Scheme for Terrain Guarding
• PTAS for geometric hitting set problems via local search
• A Constant‐Factor Approximation Algorithm for Optimal 1.5D Terrain Guarding
• Approximation Algorithms for Rectangle Stabbing and Interval Stabbing Problems

This page was built for publication: Guarding 1.5D terrains with demands