Practical Approaches to Partially Guarding a Polyhedral Terrain

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
    @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},
    }