Guarding curvilinear art galleries with edge or mobile guards via 2-dominance of triangulation graphs (Q709066): Difference between revisions

The authors study the problem of monitoring an art gallery modelled as a polygon, the edges of which are arcs of curves, with edge or mobile guards [cf. \textit{O. J'Rouke}, Art gallery theorems and algorithms. The International Series of Monographs on Computer Science, 3. New York-Oxford: Oxford University Press. (1987; Zbl 0653.52001)]. The problem is first transformed to the problem of 2-dominating a constrained triangulation graph. Once a 2-dominating set \(D\) has been found for the constrained triangulation graph, it is proved that either \(D\) is also a guard set for the piecewise-convex polygon or \(D\) is mapped to a mobile guard set for the piecewise-convex polygon. In the case of edge guards, the piecewise-convex polygon is actually monitored by the endpoints of the edges in the guard set. In the case of mobile guards, interior points of edges may also be needed in order to monitor the interior of the polygon (cf. O. J'Rouke, loc. cit.).