LINE-OF-SIGHT COMMUNICATION ON TERRAIN MODELS

Line-of-sight communication on topographic surfaces has relevance for several applications of Geographical Information Systems. In this pape r, we study the problem of linking a set of transceiver stations in a visibility-connected communication network, by placing a minimum numbe r of relays on the terrain surface. The problem is studied in the fram ework of a discrete visibility model, where the mutual visibility of a finite set of sites on the terrain is represented through a graph, ca lled the visibility graph. While in the special case of only two trans ceivers an optimal solution can be found in polynomial time, by comput ing a minimum path on the visibility graph, the general problem is equ ivalent to a Steiner problem on the visibility graph, and, thus, it is untractable in practice. In the latter case, we propose a practical a pproximate solution based on a Steiner heuristic. For both the special and the general case, we propose both a static and a dynamic algorith m that allow computation of a solution, and we show experimental resul ts.