Guarding orthogonal art galleries with sliding cameras (Q2401332): Difference between revisions
From MaRDI portal
Latest revision as of 09:37, 14 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Guarding orthogonal art galleries with sliding cameras |
scientific article |
Statements
Guarding orthogonal art galleries with sliding cameras (English)
0 references
8 September 2017
0 references
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.
0 references
orthogonal art galleries
0 references
sliding cameras
0 references
orthogonal polygon
0 references
minimum-cardinality sliding cameras problem
0 references
minimum-length sliding cameras problem
0 references
approximation algorithms
0 references
numerical example
0 references
0 references