Normal art galleries: Wall in – all in

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...

Full description

Saved in:
Bibliographic Details
Published in:Computational geometry : theory and applications 2013-01, Vol.46 (1), p.7-16
Main Author: Sunic, Zoran
Format: Article
Language:English
Subjects:
Algorithms
Art galleries
Corners
Galleries
Guards
Mathematical analysis
Reflexes
Visibility in polygons
Walls
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0925-7721
DOI:10.1016/j.comgeo.2012.02.007