Approximation algorithms for art gallery problems in polygons
From MaRDI portal
Publication:968202
DOI10.1016/J.DAM.2009.12.004zbMATH Open1189.52008DBLPjournals/dam/Ghosh10OpenAlexW2153108139WikidataQ56700240 ScholiaQ56700240MaRDI QIDQ968202FDOQ968202
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
Recommendations
computational geometryapproximation algorithmsgreedy algorithmsvisibility polygonsart gallery problemsminimum set cover
Cites Work
- Title not available (Why is that?)
- Approximation algorithms for combinatorial problems
- A Greedy Heuristic for the Set-Covering Problem
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- On the ratio of optimal integral and fractional covers
- A short proof of Chvatal's Watchman Theorem
- On guarding the vertices of rectilinear domains
- Traditional Galleries Require Fewer Watchmen
- Title not available (Why is that?)
- Two NP‐Hard Art‐Gallery Problems for Ortho‐Polygons
- An alternative proof of the rectilinear art gallery theorem
- A linear-time approximation algorithm for the weighted vertex cover problem
- Visibility Algorithms in the Plane
- A combinatorial theorem in plane geometry
- Title not available (Why is that?)
- Edge guards in rectilinear polygons
- An efficient algorithm for guard placement in polygons with holes
- Generalized guarding and partitioning for rectilinear polygons
- Title not available (Why is that?)
- Some NP-hard polygon decomposition problems
- Automata, Languages and Programming
- Guarding galleries and terrains
- Improved approximation algorithms for geometric set cover
- Galleries need fewer mobile guards: A variation on Chvatal's theorem
- Efficient visibility queries in simple polygons
- A 4-Approximation Algorithm for Guarding 1.5-Dimensional Terrains
- An Approximation Scheme for Terrain Guarding
- A Constant‐Factor Approximation Algorithm for Optimal 1.5D Terrain Guarding
- Visibility of disjoint polygons
- Visibility of a simple polygon
- Improved Approximations for Guarding 1.5-Dimensional Terrains
- Inapproximability results for guarding polygons and terrains
- Computational complexity of art gallery problems
- Approximation algorithms for terrain guarding.
- Decomposition of Polygons into Simpler Components: Feature Generation for Syntactic Pattern Recognition
- Title not available (Why is that?)
Cited In (30)
- A bicriteria approximation algorithm for the minimum hitting set problem in measurable range spaces
- Reliable wireless multimedia sensor network design: comparison of hybrid metaheuristics and a matheuristic
- How to guard orthogonal polygons: diagonal graphs and vertex covers
- A constant-factor approximation algorithm for vertex guarding a WV-polygon
- Reflective guarding a gallery
- Title not available (Why is that?)
- Approximability of guarding weak visibility polygons
- A Pseudopolynomial Time O(logn)-Approximation Algorithm for Art Gallery Problems
- Art Gallery Problems for Convex Nested Polygons
- A unified solving approach for two and three dimensional coverage problems in sensor networks
- A practical algorithm with performance guarantees for the art gallery problem
- Watchman tours for polygons with holes
- A 3-Approximation Algorithm for Guarding Orthogonal Art Galleries with Sliding Cameras
- How to Keep an Eye on Small Things
- An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries
- Maximizing the guarded boundary of an Art Gallery is APX-complete
- Guarding monotone art galleries with sliding cameras in linear time
- The parameterized complexity of guarding almost convex polygons
- Title not available (Why is that?)
- On orthogonally guarding orthogonal polygons with bounded treewidth
- Algorithm 966
- The art gallery theorem for polyominoes
- A nearly optimal algorithm for covering the interior of an art gallery
- Polygon guarding with orientation
- Parameterized Analysis of Art Gallery and Terrain Guarding
- Constrained Light Deployment for Reducing Energy Consumption in Buildings
- Universal Guard Problems
- An efficient algorithm for guard placement in polygons with holes
- Vertex Guarding for Dynamic Orthogonal Art Galleries
- An exact algorithm for minimizing vertex guards on art galleries
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)
