Utilize este identificador para referenciar este registo:
http://hdl.handle.net/10773/21852
Título: | Guarding orthogonal galleries with rectangular rooms |
Autor: | Bajuelos, Antonio L Bereg, Sergey Martins, Mafalda |
Palavras-chave: | Art gallery Orthogonal galleries Polygon without holes |
Data: | 1-Nov-2014 |
Editora: | Oxford University Press |
Resumo: | 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 |
Aparece nas coleções: | CIDMA - Artigos OGTCG - Artigos |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
bereg_leslie_mafalda.pdf | Main article | 291.12 kB | Adobe PDF | Ver/Abrir |
Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.