Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
414701 | Computational Geometry | 2013 | 10 Pages |
Abstract
We introduce the notion of a normal gallery, a gallery in which any configuration of guards that visually covers the walls necessarily covers the entire gallery. We show that any star gallery is normal and any gallery with at most two reflex corners is normal. A polynomial time algorithm is provided deciding if, for a given gallery and a finite set of positions within the gallery, there exists a configuration of guards in some of these positions that visually covers the walls, but not the entire gallery.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Zoran Šunić,