K-guarding of polyhedral terrain

Abstract

Site visibility analysis is an important research topic with many applications in Geographical Information Systems. This paper introduces a new paradigm in terrain guarding, called k-guarding. K-guarding is a generalization of the classic guarding problem where, instead of only one guard, each surface patch is guarded by at least k guards. Afterwards, two optimization problems based on k-guarding are defined: an optimum k-guarding, and a constrained k-guarding. There are three heuristic approaches—k-greedy add, k-stingy drop, and k-reverse greedy—that are proposed as a solution to the above-mentioned optimization problems. The first two are known approaches adapted to k-guarding, while k-reverse greedy is a new, original heuristic. The heuristics are compared using actual topographic surfaces. It is shown that our approach (k-reverse greedy) gives on average the best near optimum solutions. The most surprising finding of the experiments is that the combination of heuristics introduced here yields even better results.