Stationing guards in rectilinear art galleries
Edelsbrunner H, O’Rourke J, Welzl E. 1984. Stationing guards in rectilinear art galleries. Computer Vision, Graphics, and Image Processing. 27(2), 167–176.
Download
No fulltext has been uploaded. References only!
Journal Article
| Published
| English
Scopus indexed
Author
Edelsbrunner, HerbertISTA 
;
O'Rourke, Joseph;
Welzl, Emo
;
O'Rourke, Joseph;
Welzl, EmoAbstract
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.
Publishing Year
Date Published
1984-08-01
Journal Title
Computer Vision, Graphics, and Image Processing
Publisher
Elsevier
Volume
27
Issue
2
Page
167 - 176
ISSN
eISSN
IST-REx-ID
Cite this
Edelsbrunner H, O’Rourke J, Welzl E. Stationing guards in rectilinear art galleries. Computer Vision, Graphics, and Image Processing. 1984;27(2):167-176. doi:10.1016/S0734-189X(84)80041-9
Edelsbrunner, H., O’Rourke, J., & Welzl, E. (1984). Stationing guards in rectilinear art galleries. Computer Vision, Graphics, and Image Processing. Elsevier. https://doi.org/10.1016/S0734-189X(84)80041-9
Edelsbrunner, Herbert, Joseph O’Rourke, and Emo Welzl. “Stationing Guards in Rectilinear Art Galleries.” Computer Vision, Graphics, and Image Processing. Elsevier, 1984. https://doi.org/10.1016/S0734-189X(84)80041-9.
H. Edelsbrunner, J. O’Rourke, and E. Welzl, “Stationing guards in rectilinear art galleries,” Computer Vision, Graphics, and Image Processing, vol. 27, no. 2. Elsevier, pp. 167–176, 1984.
Edelsbrunner H, O’Rourke J, Welzl E. 1984. Stationing guards in rectilinear art galleries. Computer Vision, Graphics, and Image Processing. 27(2), 167–176.
Edelsbrunner, Herbert, et al. “Stationing Guards in Rectilinear Art Galleries.” Computer Vision, Graphics, and Image Processing, vol. 27, no. 2, Elsevier, 1984, pp. 167–76, doi:10.1016/S0734-189X(84)80041-9.
Google Scholar