Carleton University
Technical Report TR-196
October 1991
Lights, Walls and Bricks
J. Czyzowicz, E. Rivera-Campo, N. Santoro, J. Urrutia, J. Zaks
Abstract
Consider a rectangular art gallery divided into n rectangular rooms, such that any two rooms sharing a wall in common have a door connecting them. How many guards need to be stationed in the gallery so as to protect all of the rooms in our gallery? Notice that if a guard is stationed at a
door, he will be able to guard two rooms. Our main aim in this paper is to show that r n/2 l guards are always sufficient to protect all rooms in a rectangular art gallery. Extensions of our result are obtained for non rectangular galleries and for 3-dimensional art galleries.