Approximability of guarding weak visibility polygons

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

zbMATH Keywords

visibilityart gallery probleminapproximabilityconstant factor approximation algorithmvertex guardingEuclidean shortest path tree

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Distance in graphs (05C12) Approximation algorithms (68W25)

Related Items (6)

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

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Approximability of guarding weak visibility polygons