On the Number of Guards in Sculpture Garden Problem
Marzieh Eskandari, Ali Mohades, Bahram Sadeghi Bigham · Figshare · 2010
Abstract: In this paper, we consider the problem of placing a small number of angle guards inside a simple polygon P such that each point in the plane can determine if it is in or out of P from a monotone Boolean formula (and (.) and or (+) operations only) composed from the angle guards. Each angle guard views an infinite wedge of the plane. This class of new art gallery type problems is called sculpture garden problems. First we present an efficient algorithm for placing n –[c/2] angle guards inside a simple n-gon P and show that this bound is tight, where c is the number of vertices of convex hull of P. Then we show that, for any polygon P, there is a set of n –[c/2]–h angle guards that solve the sculpture garden problem for P, where h is the number of holes in P and show that this bound is tight, too.