A constant-factor approximation algorithm for optimal terrain guarding

MaRDI QIDQ2921708zbMATH OpenFDO

Authors Boaz Ben-Moshe, Joseph S. B. Mitchell, Matthew J. Katz

Publication date 13 October 2014

Mathematics Subject Classification ID

Variants of convex sets (star-shaped, ((m, n))-convex, etc.) (52A30) Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15) Approximation algorithms (68W25)

Recommendations

• A Constant‐Factor Approximation Algorithm for Optimal 1.5D Terrain Guarding
• A 4-Approximation Algorithm for Guarding 1.5-Dimensional Terrains
• Improved approximations for guarding 1.5-dimensional terrains
• Improved approximations for guarding 1.5-dimensional terrains
• An Approximation Scheme for Terrain Guarding

Cited in

(13)

• Approximation algorithms for terrain guarding.
• Parametric search: three new applications
• Altitude terrain guarding and guarding uni-monotone polygons
• On guarding the vertices of rectilinear domains
• A 4-Approximation Algorithm for Guarding 1.5-Dimensional Terrains
• An Approximation Scheme for Terrain Guarding
• Guarding 1.5D terrains with demands
• scientific article; zbMATH DE number 7236415 (Why is no real title available?)
• Improved approximations for guarding 1.5-dimensional terrains
• Improved approximations for guarding 1.5-dimensional terrains
• A Constant‐Factor Approximation Algorithm for Optimal 1.5D Terrain Guarding
• Optimal Guard Placement Problem Under L-Visibility
• Hitting sets online and unique-MAX coloring

This page was built for publication: A constant-factor approximation algorithm for optimal terrain guarding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2921708)