An O( OPT)-approximation algorithm for multi-guarding galleries
From MaRDI portal
Publication:2340409
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
Cites work
- scientific article; zbMATH DE number 4065813 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1559563 (Why is no real title available?)
- scientific article; zbMATH DE number 1830719 (Why is no real title available?)
- scientific article; zbMATH DE number 910872 (Why is no real title available?)
- scientific article; zbMATH DE number 1424310 (Why is no real title available?)
- A Greedy Heuristic for the Set-Covering Problem
- A Pseudopolynomial Time O(logn)-Approximation Algorithm for Art Gallery Problems
- A combinatorial theorem in plane geometry
- A new upper bound for the VC-dimension of visibility regions
- A short proof of Chvatal's Watchman Theorem
- A threshold of ln n for approximating set cover
- Algorithms for polytope covering and approximation
- Almost optimal set covers in finite VC-dimension
- Almost tight bounds for \(\epsilon\)-nets
- Approximation algorithms for art gallery problems in polygons
- Computational complexity of art gallery problems
- Efficient visibility queries in simple polygons
- Fast Approximation Algorithms for Fractional Packing and Covering Problems
- Fast vertex guarding for polygons with and without holes
- Guarding galleries where every point sees a large area
- Guarding galleries where no point sees a small area.
- Hitting sets when the VC-dimension is small
- Improved approximation for guarding simple galleries from the perimeter
- Inapproximability results for guarding polygons and terrains
- Learnability and the Vapnik-Chervonenkis dimension
- Note on the paper ``K-vertex guarding simple polygons
- On the set multicover problem in geometric settings
- Some NP-hard polygon decomposition problems
- Terrain guarding is NP-hard
- \(K\)-vertex guarding simple polygons
Cited in
(10)- Parameterized Analysis of Art Gallery and Terrain Guarding
- Observation routes and external watchman routes
- Improved approximation for guarding simple galleries from the perimeter
- A practical algorithm with performance guarantees for the art gallery problem
- On guarding orthogonal polygons with sliding cameras
- A Pseudopolynomial Time O(logn)-Approximation Algorithm for Art Gallery Problems
- Observation routes and external watchman routes
- Guarding orthogonal art galleries with sliding \(k\)-transmitters: hardness and approximation
- The parameterized complexity of guarding almost convex polygons
- scientific article; zbMATH DE number 7236415 (Why is no real title available?)
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)
