Article
On the Number of Guards in Sculpture Garden Problem.pdf
World Applied Sciences Journal
(2010)
Abstract
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.
Keywords
- Computational geometry,
- Art gallery,
- Sculpture garden problem,
- Wireless localization
Disciplines
Publication Date
2010
Citation Information
Marzieh Eskandari, A. Mohades and Bahram Sadeghi Bigham. "On the Number of Guards in Sculpture Garden Problem.pdf" World Applied Sciences Journal (2010) p. 1255 - 1263 ISSN: 1818-4952 Available at: http://works.bepress.com/marzieh-eskandari/10/