Guarding galleries and terrains

DOI10.1016/j.ipl.2006.05.014zbMath1185.68776OpenAlexW2110033738MaRDI QIDQ845875

Sariel Har-Peled, Alon Efrat

Publication date: 29 January 2010

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

Full work available at URL: https://doi.org/10.1016/j.ipl.2006.05.014

Mathematics Subject Classification ID

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

Related Items (22)

Parameterized Analysis of Art Gallery and Terrain Guarding ⋮ The VC-dimension of visibility on the boundary of monotone polygons ⋮ Approximate guarding of monotone and rectilinear polygons ⋮ Multi-agent deployment for visibility coverage in polygonal environments with holes ⋮ Universal Guard Problems ⋮ Polygon guarding with orientation ⋮ On the complexity of half-guarding monotone polygons ⋮ The parameterized complexity of guarding almost convex polygons ⋮ A nearly optimal algorithm for covering the interior of an art gallery ⋮ Topological art in simple galleries ⋮ Link distance and shortest path problems in the plane ⋮ Improved approximation for guarding simple galleries from the perimeter ⋮ Minimum covering with travel cost ⋮ A nearly optimal sensor placement algorithm for boundary coverage ⋮ Approximation algorithms for art gallery problems in polygons ⋮ Towards Optimal Positioning of Surveillance UGVs ⋮ The art gallery theorem for polyominoes ⋮ LOCATING GUARDS FOR VISIBILITY COVERAGE OF POLYGONS ⋮ Unnamed Item ⋮ Reliable wireless multimedia sensor network design: comparison of hybrid metaheuristics and a matheuristic ⋮ A constant-factor approximation algorithm for vertex guarding a WV-polygon ⋮ Approximability of guarding weak visibility polygons

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An alternative proof of the rectilinear art gallery theorem
• Guarding galleries where no point sees a small area.
• On the bit complexity of minimum link paths: Superquadratic algorithms for problem solvable in linear time
• An output sensitive algorithm for discrete convex hulls
• Approximation algorithms for terrain guarding.
• Almost optimal set covers in finite VC-dimension
• Pick's Theorem Revisited
• A linear algorithm for computing the visibility polygon from a point
• Some NP-hard polygon decomposition problems
• Path Planning in 0/1/∞ Weighted Regions with Applications
• An art gallery theorem for line segments in the plane
• On the combinatorial and algebraic complexity of quantifier elimination
• Algorithms for polytope covering and approximation
• A randomized art-gallery algorithm for sensor placement

This page was built for publication: Guarding galleries and terrains