Stationing guards in rectilinear art galleries

H. Edelsbrunner, J. O’Rourke, E. Welzl, Computer Vision, Graphics, and Image Processing 27 (1984) 167–176.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
; ;
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.
Publishing Year
Date Published
1984-08-01
Journal Title
Computer Vision, Graphics, and Image Processing
Volume
27
Issue
2
Page
167 - 176
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, 27(2), 167–176. 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 27, no. 2 (1984): 167–76. 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, 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, Academic Press, 1984, pp. 167–76, doi:10.1016/S0734-189X(84)80041-9.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar