Improved approximation for guarding simple galleries from the perimeter

DOI10.1007/s00454-011-9352-xzbMath1226.68122OpenAlexW2139332235MaRDI QIDQ635755

Juan-Miguel Gracia

Publication date: 23 August 2011

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-011-9352-x

zbMATH Keywords

approximation algorithmart gallery problempolygon guardingepsilon-netsperimeter guardsvertex guards

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Approximation by convex sets (52A27)

Related Items

Guarding monotone art galleries with sliding cameras in linear time ⋮ Parameterized Analysis of Art Gallery and Terrain Guarding ⋮ The VC-dimension of visibility on the boundary of monotone polygons ⋮ Universal Guard Problems ⋮ A new upper bound for the VC-dimension of visibility regions ⋮ VC-dimension of perimeter visibility domains ⋮ Reflective guarding a gallery ⋮ Constrained Light Deployment for Reducing Energy Consumption in Buildings ⋮ Near-linear approximation algorithms for geometric hitting sets ⋮ The parameterized complexity of guarding almost convex polygons ⋮ A non-linear lower bound for planar epsilon-nets ⋮ Unnamed Item ⋮ On Partial Covering For Geometric Set Systems ⋮ An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries ⋮ 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
• Guarding galleries and terrains
• Almost tight bounds for \(\epsilon\)-nets
• Guarding galleries where no point sees a small area.
• Guarding galleries where every point sees a large area
• Efficient visibility queries in simple polygons
• Almost optimal set covers in finite VC-dimension
• A threshold of ln n for approximating set cover
• Learnability and the Vapnik-Chervonenkis dimension
• A Pseudopolynomial Time O(logn)-Approximation Algorithm for Art Gallery Problems
• Computational complexity of art gallery problems
• A Greedy Heuristic for the Set-Covering Problem
• Some NP-hard polygon decomposition problems
• Small-Size $\eps$-Nets for Axis-Parallel Rectangles and Boxes
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Inapproximability results for guarding polygons and terrains