Approximation algorithms for terrain guarding.

DOI10.1016/S0020-0190(01)00255-1zbMath1052.68130MaRDI QIDQ1603553

Stephan J. Eidenbenz

Publication date: 14 July 2002

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

Computational geometryComputational complexityApproximation algorithmsTerrain guarding

Mathematics Subject Classification ID

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

Related Items (9)

Guarding galleries and terrains ⋮ A finite dominating set of cardinality \(O(k)\) and a witness set of cardinality \(O(n)\) for 1.5D terrain guarding problem ⋮ ENERGY-AWARE STAGE ILLUMINATION ⋮ GENERALIZED WATCHMAN ROUTE PROBLEM WITH DISCRETE VIEW COST ⋮ An exact algorithm for minimizing vertex guards on art galleries ⋮ Approximation algorithms for art gallery problems in polygons ⋮ Finding minimum hidden guard sets in polygons --- tight approximability results ⋮ Towards Optimal Positioning of Surveillance UGVs ⋮ Altitude terrain guarding and guarding uni-monotone polygons

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Guarding polyhedral terrains
• Approximation algorithms for combinatorial problems
• Computing the shortest watchtower of a polyhedral terrain in \(O(n\log n)\) time.
• Computational complexity of art gallery problems

This page was built for publication: Approximation algorithms for terrain guarding.