Polygon guarding with orientation (Q340539)

The paper deals with a variant of the art gallery problem in which we want to place the minimum number of cameras in order to see all faces of any convex object moving in the environment -- the \(\Delta\)-guarding problem. At the beginning the authors show that \(\Omega(\sqrt{n})\) guards are always needed to \(\Delta\)-guard any \(n\)-sided simple polygon. Then, they study the algorithmic problem of placing guards on the vertices of the polygon (vertex guards) in order to \(\Delta\)-guard a given input polygon \(P\). A \(O(\log c_{\mathrm{opt}})\) approximation algorithm is presented, where \(c_{\mathrm{opt}}\) is the minimum number of vertex guards required to \(\Delta\)-guard \(P\). In the algorithm the problem of \(\Delta\)-guarding every point in the interior of \(P\) is converted into the problem of \(\Delta\)-guarding only a finite number of points, which can be solved using a greedy set cover algorithm. Next, the authors study \(\Delta\)-guarding of chords. Chord in a simple polygon \(P\) is any line segment which joins two mutually visible points that lie on the boundary of \(P\). In the \(\Delta\)-guarding problem we have a set of chords \(C\) and we search for the minimum number of guards, and their placement, in order to \(\Delta\)-guard at least one point on each chord in \(C\). The authors present an approximation algorithm that solves this problem for any simply-connected polygon which uses at most \(12\) times the optimal number of guards.