Guarding curvilinear art galleries with edge or mobile guards
Menelaos I. Karavelas · 2008
In this paper we consider the problem of guarding an art gallery modeled as a polygon, the edges of which are arcs of curves, with edge or mobile guards. Our focus is on piecewise convex polygons, i.e., polygons the edges of which are convex arcs pointing towards the exterior of the polygon. We transform the problem of guarding a piecewise convex polygon to the problem of 2-dominating a properly defined combinatorial triangulation graph with edges or diagonals, where 2-dominance requires that every triangle in the triangulation graph has at least two of its vertices in its 2-dominating set. In this paper we show that: (1) ⌊ n+1 3 ⌋ diagonal guards are always sufficient and sometimes necessary, and (2) ⌊2n+2 5 ⌋ edge guards are always sufficient and ⌊2n 5 ⌋ edge guards are sometimes necessary, in order to 2-dominate a combinatorial triangulation graph. Using these results we then prove that: (1) ⌊ n+1 3 ⌋ mobile guards or ⌊2n+2 5 ⌋ edge guards are always sufficient, (2) ⌊ n 3 ⌋ mobile or edge guards are sometimes necessary, in order to guard a piecewise convex polygon.