Stationing guards in rectilinear art galleries Journal Article


Author(s): Edelsbrunner, Herbert; O'Rourke, Joseph; Welzl, Emo
Article Title: Stationing guards in rectilinear art galleries
Affiliation
Abstract: A rectilinear polygon can be viewed as an art gallery room whose walls meet at right angles. An algorithm is presented that stations guards in such a room so that every interior point is visible to some guard. The algorithm partitions the polygon into L-shaped pieces, a subclass of star-shaped pieces, and locates one guard within each kernel. The algorithm runs in O(n log n) time in the worst case for a polygon of n vertices.
Journal Title: Computer Vision, Graphics, and Image Processing
Volume: 27
Issue 2
ISSN: 0734-189X
Publisher: Academic Press  
Date Published: 1984-08-01
Start Page: 167
End Page: 176
DOI: 10.1016/S0734-189X(84)80041-9
Open access: no
IST Austria Authors
Related IST Austria Work