Approximability of guarding weak visibility polygons
From MaRDI portal
Publication:2357167
DOI10.1016/j.dam.2016.12.015zbMath1365.05070OpenAlexW2963195697WikidataQ56700105 ScholiaQ56700105MaRDI QIDQ2357167
Pritam Bhattacharya, Bodhayan Roy, Subir Kumar Ghosh
Publication date: 19 June 2017
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2016.12.015
visibilityart gallery probleminapproximabilityconstant factor approximation algorithmvertex guardingEuclidean shortest path tree
Extremal problems in graph theory (05C35) Paths and cycles (05C38) Distance in graphs (05C12) Approximation algorithms (68W25)
Related Items
Parameterized Analysis of Art Gallery and Terrain Guarding, Vertex Guarding for Dynamic Orthogonal Art Galleries, On the complexity of half-guarding monotone polygons, The parameterized complexity of guarding almost convex polygons, Terrain-like graphs: PTASs for guarding weakly-visible polygons and terrains, A constant-factor approximation algorithm for vertex guarding a WV-polygon
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved approximation for guarding simple galleries from the perimeter
- Characterizing and recognizing weak visibility polygons
- An alternative proof of the rectilinear art gallery theorem
- Guarding galleries and terrains
- Approximation algorithms for art gallery problems in polygons
- Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
- A short proof of Chvatal's Watchman Theorem
- A combinatorial theorem in plane geometry
- On the complexity of locating linear facilities in the plane
- On guarding the vertices of rectilinear domains
- A threshold of ln n for approximating set cover
- Traditional Galleries Require Fewer Watchmen
- Approximation Algorithms for Art Gallery Problems in Polygons and Terrains
- A Pseudopolynomial Time O(logn)-Approximation Algorithm for Art Gallery Problems
- Computational complexity of art gallery problems
- Some NP-hard polygon decomposition problems
- Two NP‐Hard Art‐Gallery Problems for Ortho‐Polygons
- Vertex Guarding in Weak Visibility Polygons
- Analytical approach to parallel repetition
- OPTIMUM GUARD COVERS AND m-WATCHMEN ROUTES FOR RESTRICTED POLYGONS
- Visibility Algorithms in the Plane
- Inapproximability results for guarding polygons and terrains
