An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries
From MaRDI portal
Publication:2340409
DOI10.1007/S00454-014-9656-8zbMath1309.68199OpenAlexW200149117MaRDI QIDQ2340409
Publication date: 16 April 2015
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00454-014-9656-8
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Related Items (6)
Parameterized Analysis of Art Gallery and Terrain Guarding ⋮ Observation routes and external watchman routes ⋮ The parameterized complexity of guarding almost convex polygons ⋮ On Guarding Orthogonal Polygons with Sliding Cameras ⋮ Guarding orthogonal art galleries with sliding \(k\)-transmitters: hardness and approximation ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A new upper bound for the VC-dimension of visibility regions
- Improved approximation for guarding simple galleries from the perimeter
- Note on the paper ``K-vertex guarding simple polygons
- Approximation algorithms for art gallery problems in polygons
- \(K\)-vertex guarding simple polygons
- Hitting sets when the VC-dimension is small
- Almost tight bounds for \(\epsilon\)-nets
- A short proof of Chvatal's Watchman Theorem
- Guarding galleries where no point sees a small area.
- Guarding galleries where every point sees a large area
- A combinatorial theorem in plane geometry
- Efficient visibility queries in simple polygons
- Almost optimal set covers in finite VC-dimension
- Fast vertex guarding for polygons with and without holes
- On the set multicover problem in geometric settings
- Terrain Guarding is NP-Hard
- 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
- Fast Approximation Algorithms for Fractional Packing and Covering Problems
- Algorithms for polytope covering and approximation
- Inapproximability results for guarding polygons and terrains
This page was built for publication: An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries
