## Abstract

Let P be an orthogonal polygon with n vertices. A sliding camera travels back and forth along an orthogonal line segment

s⊆P

corresponding to its trajectory. The camera sees a point

p∈P

if there is a point

q∈s

such that

pq‾

is a line segment normal to s that is completely contained in P. In the Minimum-Cardinality Sliding Cameras (MCSC) problem, the objective is to find a set S of sliding cameras of minimum cardinality to guard P (i.e., every point in P can be seen by some sliding camera in S), while in the Minimum-Length Sliding Cameras (MLSC) problem the goal is to find such a set S so as to minimize the total length of trajectories along which the cameras in S travel.

In this paper, we answer questions posed by Katz and Morgenstern (2011) by presenting the following results: (i) the MLSC problem is polynomially tractable even for orthogonal polygons with holes, (ii) the MCSC problem is NP-complete when P is allowed to have holes, and (iii) an

O(n3logn)

-time 2-approximation algorithm for the MCSC problem on [NE]-star-shaped orthogonal polygons with n vertices (similarly, [NW]-, [SE]-, or [SW]-star-shaped orthogonal polygons).

s⊆P

corresponding to its trajectory. The camera sees a point

p∈P

if there is a point

q∈s

such that

pq‾

is a line segment normal to s that is completely contained in P. In the Minimum-Cardinality Sliding Cameras (MCSC) problem, the objective is to find a set S of sliding cameras of minimum cardinality to guard P (i.e., every point in P can be seen by some sliding camera in S), while in the Minimum-Length Sliding Cameras (MLSC) problem the goal is to find such a set S so as to minimize the total length of trajectories along which the cameras in S travel.

In this paper, we answer questions posed by Katz and Morgenstern (2011) by presenting the following results: (i) the MLSC problem is polynomially tractable even for orthogonal polygons with holes, (ii) the MCSC problem is NP-complete when P is allowed to have holes, and (iii) an

O(n3logn)

-time 2-approximation algorithm for the MCSC problem on [NE]-star-shaped orthogonal polygons with n vertices (similarly, [NW]-, [SE]-, or [SW]-star-shaped orthogonal polygons).

Original language | English |
---|---|

Pages (from-to) | 12-26 |

Number of pages | 15 |

Journal | Computational Geometry |

Volume | 65 |

Issue number | October 2017 |

DOIs | |

Publication status | Published - 1 Oct 2017 |

## Keywords

- Approximation algorithms
- Orthogonal art galleries
- Sliding cameras