An efficient algorithm to compute the viewshed on DEM terrains stored in the external memory
Biblioteca Digital da Memória Científica do INPE (National Institute for Space Research)Published 1 January 2007Open access
Mirella Antunes de Magalhães, Salles V. G. Magalhães, Marcus V. A. Andrade, Jugurta Lisboa Filho
Citations9
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper presents an efficient algorithm to compute the viewshed on terrains stored in the external memory that outperforms the known algorithms described in the literature.
Abstract
Abstract. Nowadays, there is a huge volume of data about terrains available and generally, these data do not fit in the internal memory. So, many GIS applications require efficient algorithms to manipulate the data externally. One of these applications is the viewshed computation that consists in obtain the visible points from a given point p. In this paper, we present an efficient algorithm to compute the viewshed on terrains stored in the external memory. The algorithm complexity is O(scan(N)) where N is the number of points in a DEM and scan(N) is the minimum number of I/O operations required to read N contiguous items stored in the external memory. Also, as shown in the results, our algorithm outperforms the known algorithms described in the literature. 1.
Keywords
Computer ScienceEnvironmental Science
Communications of the ACMThe input/output complexity of sorting and related problems
1,240 Citations1988Alok Aggarwal, Jeffrey,S. Vitter
Tight upper and lower bounds are provided for the number of inputs and outputs (I/OS) between internal memory and secondary storage required for five sorting-related problems: sorting, the fast Fourier transform (FFT), permutation networks, permuting, and matrix transposition.
Digital Terrain Modeling: Principles and Methodology
488 Citations2004Zhilin Li, Christopher Zhu +1 more
Multi-Scale Representation of Digital Elevation Models and DTM-Based Terrain Analysis (DTM Interpretation).
External-memory computational geometry
195 Citations2002Michael T. Goodrich, Jyh-Jong Tsay +2 more
New techniques for designing efficient algorithms for computational geometry problems that are too large to be solved in internal memory are given and these algorithms are the first known optimal algorithms for a wide range of two-level and hierarchical multilevel memory models, including parallel models.
International Journal of Geographical Information SystemsOn applying viewshed analysis for determining least-cost paths on Digital Elevation Models
180 Citations1998JAY LEE DAN STUCKY
This paper presents the implementations of least-cost paths by integrating viewshed information computed from digital elevation models, and includes four possible types of paths.
Computers Environment and Urban SystemsModelling environmental influences on property prices in an urban environment
138 Citations1998Iain Lake, Andrew Lovett +2 more
Cartographica The International Journal for Geographic Information and GeovisualizationAn Intensive Comparison of Triangulated Irregular Networks (TINs) and Digital Elevation Models (DEMs)
124 Citations1994Mark P. Kumler
Environment and Planning B Planning and DesignAlgorithms for Visibility Computation on Terrains: A Survey
120 Citations2003Leila De Floriani, Paola Magillo
In this paper, the authors consider a number of visibility problems on terrains and present an overview of algorithms to tackle such problems on triangulated irregular networks and regular square grids.
IEEE Transactions on Visualization and Computer GraphicsFast horizon computation at all points of a terrain with visibility and shading applications
72 Citations1998A. James Stewart
Experimental and theoretical results are presented which show that the algorithm is more accurate that previous algorithms and is faster than previous algorithms in terrains of more than 100,000 sample points.
Information Processing LettersApproximation algorithms for terrain guarding
66 Citations2002Stephan Eidenbenz
These approximation algorithms transform the terrain guarding instance into a MINIMUM SET COVER instance, which is then solved by the standard greedy approximation algorithm, which achieves approximation ratios of O(logn), where n is the number of vertices in the input terrain.
Lecture notes in computer scienceStxxl: Standard Template Library for XXL Data Sets
63 Citations2005Roman Dementiev, Lutz Kettner +1 more
Stxxl is an implementation of the C++ standard template library STL for external memory computations that supports parallel disks, overlapping between I/O and computation, and pipelining technique that can save more than half of the I/Os.
Siting Observers on Terrain
57 Citations2002Wm. Randolph Franklin
An experimental study of a new algorithm that synthesises separate programs, for fast viewshed, and for fast approximate visibility index determination, implemented in a working testbed for siting multiple observers jointly to cover terrain from a full level-1 DEM.
SIAM Journal on ComputingA Constant‐Factor Approximation Algorithm for Optimal 1.5D Terrain Guarding
51 Citations2007Boaz Ben‐Moshe, Matthew J. Katz +1 more
This work gives the first constant-factor approximation algorithm for a nontrivial instance of the optimal guarding (coverage) problem in polygons, and gives an $O(1)$-approximation algorithm for placing the fewest point guards on a 1.5D terrain.
Variations on sweep algorithms: efficient computation of extended viewsheds and class intervals
45 Citations1996Marc van Kreveld
Two novel applications of the plane sweep paradigm are demonstrated, namely, for the computation of extended viewsheds on gridded DEMs and for class interval selection on TIN-based DEMs.
AlgorithmicaExternal-Memory Algorithms for Processing Line Segments in Geographic Information Systems
34 Citations2006Lars Arge, Darren Erik Vengroff +1 more
This paper develops efficient external-memory algorithms for a number of important problems involving line segments in the plane, including trapezoid decomposition, batched planar point location, triangulation, red--blue line segment intersection reporting, and general line segments intersection reporting.
Visibility preserving terrain simplification
29 Citations2002Boaz Ben‐Moshe, Joseph S. B. Mitchell +2 more
This work proposes a new method of simplifying terrain surfaces, designed specifically to maximize a new measure of quality based on preserving inter-point visibility relationships, and experimentally compares its performance with that of other leading simplification methods.
Tradeoffs when Multiple Observer Siting on Large Terrain Cells
27 Citations2006W. Randolph Franklin, Christian Vogt
A toolkit for multiple observer siting to maximize their joint viewshed, on high-resolution gridded terrains, up to 2402 × 2402, with the viewsheds’ radii of up to 1000 shows that approximate (rather than exact) visibility indexes of observers are sufficient for siting multiple observers.
Journal of HeuristicsAutomated antenna positioning algorithms for wireless fixed-access networks
24 Citations2007Yehuda Ben‐Shimol, Boaz Ben‐Moshe +3 more
This paper suggests several alternative automated heuristics, relying on terrain preprocessing to find educated potential points for positioning relay stations, and indicates that for small networks, the results obtained by human experts are adequate although they rarely exceed the quality of automated alternatives.
Lecture notes in computer scienceOn the Planar Two-Watchtower Problem
16 Citations2001Sergei Bespamyatnikh, Zhixiang Chen +2 more
An O(n4) time algorithm is presented to solve the discrete version of this problem when v, v′ must be on some vertices of T when the maximum height of uv, u′v′ is minimized.
GeoInformaticaApproximating the Visible Region of a Point on a Terrain
5 Citations2007Boaz Ben‐Moshe, Paz Carmi +1 more
A generic radar-like algorithm for computing an approximation of Rp, which interpolates the visible region between two consecutive rays whenever the rays are close enough; that is, whenever the difference between the sets of visible segments along the cross sections in the directions specified by the rays is below some threshold.
Society for Industrial and Applied Mathematics eBooksComputing Visibility on Terrains in External Memory
3 Citations2007Herman Haverkort, Laura Toma +1 more