An O( OPT)-approximation algorithm for multi-guarding galleries
From MaRDI portal
Publication:2340409
DOI10.1007/S00454-014-9656-8zbMATH Open1309.68199OpenAlexW200149117MaRDI QIDQ2340409FDOQ2340409
Authors: David Kirkpatrick 
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
Recommendations
- Improved approximation for guarding simple galleries from the perimeter
- An approximation algorithm for the art gallery problem
- A Pseudopolynomial Time O(logn)-Approximation Algorithm for Art Gallery Problems
- Approximation algorithms for art gallery problems in polygons
- Approximability of guarding weak visibility polygons
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Cites Work
- A threshold of ln n for approximating set cover
- Title not available (Why is that?)
- A Greedy Heuristic for the Set-Covering Problem
- Learnability and the Vapnik-Chervonenkis dimension
- Hitting sets when the VC-dimension is small
- Almost tight bounds for \(\epsilon\)-nets
- A short proof of Chvatal's Watchman Theorem
- Almost optimal set covers in finite VC-dimension
- Terrain guarding is NP-hard
- Title not available (Why is that?)
- Title not available (Why is that?)
- Approximation algorithms for art gallery problems in polygons
- A combinatorial theorem in plane geometry
- Title not available (Why is that?)
- Title not available (Why is that?)
- Algorithms for polytope covering and approximation
- Some NP-hard polygon decomposition problems
- Guarding galleries where no point sees a small area.
- Guarding galleries where every point sees a large area
- A new upper bound for the VC-dimension of visibility regions
- Improved approximation for guarding simple galleries from the perimeter
- Fast Approximation Algorithms for Fractional Packing and Covering Problems
- Title not available (Why is that?)
- \(K\)-vertex guarding simple polygons
- Efficient visibility queries in simple polygons
- A Pseudopolynomial Time O(logn)-Approximation Algorithm for Art Gallery Problems
- Inapproximability results for guarding polygons and terrains
- Computational complexity of art gallery problems
- Note on the paper ``K-vertex guarding simple polygons
- Fast vertex guarding for polygons with and without holes
- On the set multicover problem in geometric settings
Cited In (10)
- On guarding orthogonal polygons with sliding cameras
- Improved approximation for guarding simple galleries from the perimeter
- A Pseudopolynomial Time O(logn)-Approximation Algorithm for Art Gallery Problems
- Guarding orthogonal art galleries with sliding \(k\)-transmitters: hardness and approximation
- A practical algorithm with performance guarantees for the art gallery problem
- Observation routes and external watchman routes
- Observation routes and external watchman routes
- The parameterized complexity of guarding almost convex polygons
- Parameterized Analysis of Art Gallery and Terrain Guarding
- Title not available (Why is that?)
This page was built for publication: An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2340409)
