Back to Search
Start Over
Line-of-sight communication on terrain models
- Publication Year :
- 1994
- Publisher :
- TAYLOR & FRANCIS LTD, 1994.
-
Abstract
- Line-of-sight communication on topographic surfaces has relevance for several applications of Geographical Information Systems. In this paper, we study the problem of linking a set of transceiver stations in a visibility-connected communication network, by placing a minimum number of relays on the terrain surface. The problem is studied in the framework of a discrete visibility model, where the mutual visibility of a finite set of sites on the terrain is represented through a graph, called the visibility graph. While in the special case of only two transceivers an optimal solution can be found in polynomial time, by computing a minimum path on the visibility graph, the general problem is equivalent to a Steiner problem on the visibility graph, and, thus, it is untractable in practice. In the latter case, we propose a practical approximate solution based on a Steiner heuristic. For both the special and the general case, we propose both a static and a dynamic algorithm that allow computation of a s...
- Subjects :
- Theoretical computer science
Heuristic (computer science)
Visibility graph
Geography, Planning and Development
Visibility (geometry)
Library and Information Sciences
Steiner tree problem
symbols.namesake
Dynamic problem
Path (graph theory)
symbols
General Earth and Planetary Sciences
Graph (abstract data type)
Time complexity
ComputingMethodologies_COMPUTERGRAPHICS
Information Systems
Mathematics
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....b706dfc20f63fba9a5320644c0236896