On the Complexity of Half-Guarding Monotone Polygons

2022/04/27 by Hillberg, Hannah Miller, Krohn, Erik, Pahlow, Alex · 1 citation
#Computational Geometry (cs.CG) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2204.13143

Abstract

We consider a variant of the art gallery problem where all guards are limited to seeing to the right inside a monotone polygon. We call such guards: half-guards. We provide a polynomial-time approximation for point guarding the entire monotone polygon. We improve the best known approximation of 40 from [11], to 8. We also provide an NP-hardness reduction for point guarding a monotone polygon with half-guards.

Cited by

• The Contiguous Art Gallery Problem is in Θ(n log n)

Related

• Opposing Half Guards
• Implementation of polygon guarding algorithms for art gallery problems
• Constant Approximation Algorithms for Guarding Simple Polygons using Vertex Guards
• Approximability of Guarding Weak Visibility Polygons
• Lower Bound for Sculpture Garden Problem