Guarding orthogonal art galleries with sliding cameras (Q2401332): Difference between revisions

The paper deals with a variant of the orthogonal art gallery problem where an orthogonal polygon \(P\) has to be covered with the union of the visibility regions of a set of sliding cameras. The sliding camera travels along an orthogonal line segment trajectory lying in \(P\). The sliding camera sees all points in \(P\) from which a normal line to the trajectory can be constructed such that the normal line belongs to \(P\). The authors are focused on the two following problems: the MCSC (minimum-cardinality sliding cameras) problem where the number of sliding cameras necessary to guard \(P\) completely is minimized, and the MLSC (minimum-length sliding cameras) problem where the total length of trajectories of all cameras is minimized. Specially, a polynomial-time algorithm that solves the MLSC problem exactly even for orthogonal polygons with holes is given. Next, the authors show that the MCSC problem is NP-complete when \(P\) contains holes and give an \(O(n^3\log n)\)-time 2-approximation algorithm for the MCSC problem on [X]-star-shaped polygons with \(n\) vertices. The paper is completed by examples that illustrate very well the problem solved.