On Half Guarding Polygons

Given a polygon P and a set of potential guard locations \(G \in P\) , the art gallery problem asks for the minimum number of guards needed to guard the polygon. The art gallery problem with different types of polygons has been studied extensively. Variants of the art gallery problem have also been studied including limiting the polygon to be a monotone or an orthogonal polygon. Limitations have also been applied to the guard where a guard cannot see 360° and even limitations on the distance a guard can see. In this paper, we study the art gallery problem using half guards (guards that see 180°) in various settings. We show that the VC dimension of half guarding a terrain is exactly 2 or 3, depending on certain assumptions, and exactly 4 with half guarding a monotone polygon where all critical points are located on the boundary. We provide so-called art gallery theorems for half guards with different polygon types. Finally, we provide a linear time exact algorithm for half guarding a spiral polygon.