Guarding orthogonal galleries with rectangular rooms Article

Bajuelos, AL, Bereg, S, Martins, M. (2013). Guarding orthogonal galleries with rectangular rooms . COMPUTER JOURNAL, 57(11), 1668-1673. 10.1093/comjnl/bxt089

cited authors

  • Bajuelos, AL; Bereg, S; Martins, M

abstract

  • Consider an orthogonal art gallery partitioned into n rectangular rooms. If two rooms are adjacent, there is a door connecting them and a guard positioned at this door will see both rooms. In Czyzowicz et al. [(1994) Guarding rectangular art galleries. Discrete Appl. Math., 50, 149-157], it is shown that any rectangular gallery can be guarded with ⌈n/2⌉ guards. We prove that the same bound holds for L-shape polygons. We extend it to staircases and prove that an orthogonal staircase with n rooms and r reflex vertices can be guarded with ⌈(n+⌊ r/2⌋)/2⌉ guards. Then we prove an upper bound on the number of guards for arbitrary orthogonal polygon with orthogonal holes. This result improves the previous bound by Czyzowicz et al. [(1994) Guarding rectangular art galleries. Discrete Appl. Math., 50, 149-157] (even in the case of polygon without holes).

publication date

  • June 17, 2013

published in

Digital Object Identifier (DOI)

start page

  • 1668

end page

  • 1673

volume

  • 57

issue

  • 11