Guarding rectangular art galleries

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 the present gallery? Note that if a guard is stationed at a door, he will be able to guard two rooms. The main aim in this paper is to show that ⌈n/2⌉ guards are always sufficient to protect all rooms in a rectangular art gallery. Extensions of the present result are obtained for non-rectangular galleries and for 3-dimensional art galleries.