A constant-factor approximation algorithm for vertex guarding a WV-polygon

DOI10.1007/978-3-030-80879-2_6OpenAlexW3184578342MaRDI QIDQ2117689

Matthew J. Katz, Omrit Filtser, Stav Ashur

Publication date: 22 March 2022

Full work available at URL: https://arxiv.org/abs/1907.01228

zbMATH Keywords

visibilityapproximation algorithmsgeometric optimizationart gallery problems

Mathematics Subject Classification ID

Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved approximation for guarding simple galleries from the perimeter
• Characterizing and recognizing weak visibility polygons
• Guarding galleries and terrains
• Approximation algorithms for art gallery problems in polygons
• Corrections to Lee's visibility polygon algorithm
• Approximability of guarding weak visibility polygons
• Approximate guarding of monotone and rectilinear polygons
• Guarding terrains via local search
• Visibility of a simple polygon
• A Pseudopolynomial Time O(logn)-Approximation Algorithm for Art Gallery Problems
• Computational complexity of art gallery problems
• Some NP-hard polygon decomposition problems
• The art gallery problem is ∃ ℝ-complete
• PTAS for geometric hitting set problems via local search
• Terrain-like graphs: PTASs for guarding weakly-visible polygons and terrains
• Inapproximability results for guarding polygons and terrains

This page was built for publication: A constant-factor approximation algorithm for vertex guarding a WV-polygon