The object of this web page is to allow the reader to learn about lower bounds on guard placement on polyhedral terrains and linear time algorithms that achieve a weaker bound. Guard placement on polyhedral terrains is an extension to three dimensions of art gallery theorems.

The site is based on the article Guarding polyhedral terrains, published in 1995 by Bose, Shermer, Toussaint and Zhu. A link to the citeseer reference for this paper can be found under the Links section, which contains the complete proofs for the lower bounds.

The first section introduces the reader to the background of art gallery theorems and lower bounds on guard placement in two dimensions. Following this is a description of the equivalent problem in three dimensions, namely Guarding polyhedral terrains. We then proceed to a simplified proof for the lower bounds on the necessary number of guards, and then to the linear time algorithms proposed by the authors for placing such guards. The last section shows an applet that allows the user to understand how the guards can be placed on a terrain.