Please use this identifier to cite or link to this item: http://hdl.handle.net/10773/21852
Title: Guarding orthogonal galleries with rectangular rooms
Author: Bajuelos, Antonio L
Bereg, Sergey
Martins, Mafalda
Keywords: Art gallery
Orthogonal galleries
Polygon without holes
Issue Date: 1-Nov-2014
Publisher: Oxford University Press
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).
Peer review: yes
URI: http://hdl.handle.net/10773/21852
DOI: 10.1093/comjnl/bxt089
ISSN: 0010-4620
Appears in Collections:CIDMA - Artigos
OGTCG - Artigos

Files in This Item:
File Description SizeFormat 
bereg_leslie_mafalda.pdfMain article291.12 kBAdobe PDFView/Open


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.