K-guarding of polyhedral terrain |
| |
Authors: | Branko KaučIč Borut Žalik |
| |
Affiliation: | 1. University of Maribor, Faculty of Education , Department of Mathematics , Koro?ka c. 160, SI 2000 Maribor, Slovenia;2. University of Maribor, Faculty of Electrical Engineering &3. Computer Sciences , Department of Computer Science , Koro?ka c. 160, SI 2000 Maribor, Slovenia |
| |
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. |
| |
Keywords: | |
|
|