Abstract

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.

Corresponding Publications

Practical Approaches to Partially Guarding a Polyhedral Terrain

Frank Kammer, Maarten Löffler, Paul Mutser, Frank Staals

Proc. 8th International Conference on Geographic Information Science, 2014

Download Local Copy View Slides Export Citation

@incollection{siting2014,
  author = {Kammer, Frank and L{\"o}ffler, Maarten and Mutser, Paul and
                 Staals, Frank},
  title = {Practical Approaches to Partially Guarding a Polyhedral Terrain},
  booktitle = {Proc. 8th International Conference on Geographic Information Science},
  year = {2014},
  series = {LNCS},
  volume = {8728},
  url = {https://dx.doi.org/10.1007/978-3-319-11593-1_21},
  doi = {10.1007/978-3-319-11593-1_21},
  location = {Vienna, Austria},
  pages = {318--332},
  numpages = {15},
  publisher = {Springer},
  category = {terrains},
}