Approximation algorithms for art gallery problems in polygons
From MaRDI portal
Publication:968202
DOI10.1016/j.dam.2009.12.004zbMath1189.52008OpenAlexW2153108139WikidataQ56700240 ScholiaQ56700240MaRDI QIDQ968202
Publication date: 5 May 2010
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2009.12.004
computational geometryapproximation algorithmsgreedy algorithmsart gallery problemsvisibility polygonsminimum set cover
Related Items
Guarding monotone art galleries with sliding cameras in linear time ⋮ Parameterized Analysis of Art Gallery and Terrain Guarding ⋮ A unified solving approach for two and three dimensional coverage problems in sensor networks ⋮ Universal Guard Problems ⋮ Polygon guarding with orientation ⋮ Vertex Guarding for Dynamic Orthogonal Art Galleries ⋮ On orthogonally guarding orthogonal polygons with bounded treewidth ⋮ A 3-Approximation Algorithm for Guarding Orthogonal Art Galleries with Sliding Cameras ⋮ Reflective guarding a gallery ⋮ Constrained Light Deployment for Reducing Energy Consumption in Buildings ⋮ Watchman tours for polygons with holes ⋮ The parameterized complexity of guarding almost convex polygons ⋮ Algorithm 966 ⋮ An exact algorithm for minimizing vertex guards on art galleries ⋮ The art gallery theorem for polyominoes ⋮ Reliable wireless multimedia sensor network design: comparison of hybrid metaheuristics and a matheuristic ⋮ An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries ⋮ How to Keep an Eye on Small Things ⋮ A constant-factor approximation algorithm for vertex guarding a WV-polygon ⋮ How to guard orthogonal polygons: diagonal graphs and vertex covers ⋮ Approximability of guarding weak visibility polygons
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An alternative proof of the rectilinear art gallery theorem
- Guarding galleries and terrains
- Improved approximation algorithms for geometric set cover
- Galleries need fewer mobile guards: A variation on Chvatal's theorem
- Visibility of disjoint polygons
- Approximation algorithms for combinatorial problems
- On the ratio of optimal integral and fractional covers
- A short proof of Chvatal's Watchman Theorem
- Edge guards in rectilinear polygons
- An efficient algorithm for guard placement in polygons with holes
- A combinatorial theorem in plane geometry
- Approximation algorithms for terrain guarding.
- Efficient visibility queries in simple polygons
- Generalized guarding and partitioning for rectilinear polygons
- On guarding the vertices of rectilinear domains
- Visibility of a simple polygon
- Traditional Galleries Require Fewer Watchmen
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- A 4-Approximation Algorithm for Guarding 1.5-Dimensional Terrains
- An Approximation Scheme for Terrain Guarding
- Computational complexity of art gallery problems
- A Greedy Heuristic for the Set-Covering Problem
- A linear-time approximation algorithm for the weighted vertex cover problem
- Some NP-hard polygon decomposition problems
- Decomposition of Polygons into Simpler Components: Feature Generation for Syntactic Pattern Recognition
- Two NP‐Hard Art‐Gallery Problems for Ortho‐Polygons
- Improved Approximations for Guarding 1.5-Dimensional Terrains
- A Constant‐Factor Approximation Algorithm for Optimal 1.5D Terrain Guarding
- Visibility Algorithms in the Plane
- Automata, Languages and Programming
- Inapproximability results for guarding polygons and terrains
