Practical Approaches to Partially Guarding a Polyhedral Terrain

We study the problem of placing guard towers on a terrain such that the terrain can be seen from at least one tower. This problem is important in many applications, and has an extensive history in the literature (known as, e.g., multiple observer siting). In this paper, we consider the problem on polyhedral terrains, and we allow the guards to see only a fixed fraction of the terrain, rather than everything. We experimentally evaluate how the number of required guards relates to the fraction of the terrain that can be covered. In addition, we introduce the concept of dominated guards, which can be used to preprocess the potential guard locations and speed up the subsequent computations.

keywords: Computational Geometry, Geographical Information Analysis, Terrains

Conference Proceedings (peer-reviewed)

Frank Kammer, Frank Staals, Maarten Löffler, Paul Mutser
Practical Approaches to Partially Guarding a Polyhedral Terrain
Proc. 8th International Conference on Geographic Information Science
LNCS 8728, 318–332, 2014
http://dx.doi.org/10.1007/978-3-319-11593-1_21

back to list