Abstract
The Rectilinear Art Gallery Theorem states that for a rectilinear art gallery with nwalls at most [n/4] guards are needed to keep the entire art gallery under observation. There have been two proofs of this result. The first proof depends on the quadrilateralization of the art gallery and is quite complicated. The second proof is direct, yet it depends on a graph-theoretic argument at one crucial point. Our proof, on the other hand, is direct, completely geometrical, and at the same time, simple.
C.R. Category:
‡This work was carried out while the second author was visiting the University of Helsinki. This visit was made possible by a grant from the Academy of Finland and by a travel grant from the Natural Sciences and Engineering Research Council of Canada. The preparation of this paper was supported by Natural Sciences and Engineering Research Council of Canada Grant No. A-5692.
‡This work was carried out while the second author was visiting the University of Helsinki. This visit was made possible by a grant from the Academy of Finland and by a travel grant from the Natural Sciences and Engineering Research Council of Canada. The preparation of this paper was supported by Natural Sciences and Engineering Research Council of Canada Grant No. A-5692.
Notes
‡This work was carried out while the second author was visiting the University of Helsinki. This visit was made possible by a grant from the Academy of Finland and by a travel grant from the Natural Sciences and Engineering Research Council of Canada. The preparation of this paper was supported by Natural Sciences and Engineering Research Council of Canada Grant No. A-5692.