Guarding orthogonal art galleries with sliding cameras

S. Durocher , O. Filtser , R. Fraser, A.D. Mehrabi, S. Mehrabi

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)

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(n3log⁡n)
-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 languageEnglish
Pages (from-to)12-26
Number of pages15
JournalComputational Geometry
Volume65
Issue numberOctober 2017
DOIs
Publication statusPublished - 1 Oct 2017

Keywords

  • Approximation algorithms
  • Orthogonal art galleries
  • Sliding cameras

Fingerprint Dive into the research topics of 'Guarding orthogonal art galleries with sliding cameras'. Together they form a unique fingerprint.

  • Cite this

    Durocher , S., Filtser , O., Fraser, R., Mehrabi, A. D., & Mehrabi, S. (2017). Guarding orthogonal art galleries with sliding cameras. Computational Geometry, 65(October 2017), 12-26 . https://doi.org/10.1016/j.comgeo.2017.04.001