GUARDING RECTANGULAR ART-GALLERIES

Consider a rectangular art gallery divided into n rectangular rooms, s uch 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 pr otect all of the rooms in our gallery? Note that if a guard is station ed at a door, he will be able to guard two rooms. Our main aim in this paper is to show that inverted right perpendicular n/2 inverted left perpendicular guards are always sufficient to protect all rooms in a r ectangular art gallery. Extensions of our result are obtained for non- rectangular galleries and for 3-dimensional art galleries.