Approximation algorithms for art gallery problems in polygons
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 3645023 (Why is no real title available?)
- scientific article; zbMATH DE number 4060719 (Why is no real title available?)
- 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 1424310 (Why is no real title available?)
- A 4-Approximation Algorithm for Guarding 1.5-Dimensional Terrains
- A Constant‐Factor Approximation Algorithm for Optimal 1.5D Terrain Guarding
- A Greedy Heuristic for the Set-Covering Problem
- A combinatorial theorem in plane geometry
- A linear-time approximation algorithm for the weighted vertex cover problem
- A short proof of Chvatal's Watchman Theorem
- An Approximation Scheme for Terrain Guarding
- An alternative proof of the rectilinear art gallery theorem
- An efficient algorithm for guard placement in polygons with holes
- Approximation algorithms for combinatorial problems
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Approximation algorithms for terrain guarding.
- Automata, Languages and Programming
- Computational complexity of art gallery problems
- Decomposition of Polygons into Simpler Components: Feature Generation for Syntactic Pattern Recognition
- Edge guards in rectilinear polygons
- Efficient visibility queries in simple polygons
- Galleries need fewer mobile guards: A variation on Chvatal's theorem
- Generalized guarding and partitioning for rectilinear polygons
- Guarding galleries and terrains
- Improved approximation algorithms for geometric set cover
- Improved approximations for guarding 1.5-dimensional terrains
- Inapproximability results for guarding polygons and terrains
- On guarding the vertices of rectilinear domains
- On the ratio of optimal integral and fractional covers
- Some NP-hard polygon decomposition problems
- Traditional Galleries Require Fewer Watchmen
- Two NP‐Hard Art‐Gallery Problems for Ortho‐Polygons
- Visibility Algorithms in the Plane
- Visibility of a simple polygon
- Visibility of disjoint polygons
Cited in
(33)- scientific article; zbMATH DE number 219237 (Why is no real title available?)
- How to Keep an Eye on Small Things
- A nearly optimal algorithm for covering the interior of an art gallery
- A bicriteria approximation algorithm for the minimum hitting set problem in measurable range spaces
- Parameterized Analysis of Art Gallery and Terrain Guarding
- A constant-factor approximation algorithm for vertex guarding a WV-polygon
- Reflective guarding a gallery
- On orthogonally guarding orthogonal polygons with bounded treewidth
- scientific article; zbMATH DE number 2011842 (Why is no real title available?)
- Vertex guarding for dynamic orthogonal art galleries
- Reliable wireless multimedia sensor network design: comparison of hybrid metaheuristics and a matheuristic
- Approximability of guarding weak visibility polygons
- Constrained light deployment for reducing energy consumption in buildings
- Universal guard problems
- Art Gallery Problems for Convex Nested Polygons
- An approximation algorithm for the art gallery problem
- Improved approximation for guarding simple galleries from the perimeter
- The art gallery theorem for polyominoes
- Algorithm 966: A practical iterative algorithm for the art gallery problem using integer linear programming
- An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries
- A practical algorithm with performance guarantees for the art gallery problem
- A Pseudopolynomial Time O(logn)-Approximation Algorithm for Art Gallery Problems
- Maximizing the guarded boundary of an Art Gallery is APX-complete
- An efficient algorithm for guard placement in polygons with holes
- Fast vertex guarding for polygons with and without holes
- Watchman tours for polygons with holes
- Vertex guarding in weak visibility polygons
- An exact algorithm for minimizing vertex guards on art galleries
- Polygon guarding with orientation
- How to guard orthogonal polygons: diagonal graphs and vertex covers
- Guarding monotone art galleries with sliding cameras in linear time
- A unified solving approach for two and three dimensional coverage problems in sensor networks
- The parameterized complexity of guarding almost convex polygons
This page was built for publication: Approximation algorithms for art gallery problems in polygons
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q968202)
