# Computing visibility on terrains in external memory

- Authors
- Publisher
- SIAM
- Publication Date
- Source
- Legacy
- Disciplines

## Abstract

Computing Visibility on Terrains in External Memory Herman Haverkort∗ Laura Toma† Yi Zhuang‡ Abstract We describe a novel application of the distribution sweeping technique to computing visibility on terrains. Given an arbi- trary viewpoint v, the basic problem we address is computing the visibility map or viewshed of v, which is the set of points in the terrain that are visible from v. We give the first I/O- efficient algorithm to compute the viewshed of v on a grid terrain in external memory. Our algorithm is based on Van Kreveld’s O(n lgn) time algorithm for the same problem in internal memory. It uses O(sort(n)) I/Os, where sort(n) is the complexity of sorting n items of data in the I/O-model. We present an implementation and experimental evaluation of the algorithm. Our implementation clearly outperforms the previous (in-memory) algorithms and can compute visi- bility for terrains of up to 4GB in a few hours on a low-cost machine. 1 Introduction In this paper we consider the problem of computing visibility on very large terrains in external memory. Given an arbitrary viewpoint v and a terrain, the basic problem we address is computing the visibility map or viewshed of v, which is the set of points in the terrain that are visible from v (Figure 1). Visibility has applications in graphics and game design, and mainly in Geographic Information Systems (GIS), ranging from path planning, navigation, landscaping, to placement of fire towers, radar sites and cellphone towers [12, 16]. Visibility has been widely studied in computational geometry and graphics; for a survey of the various problems and results see Cole and Sharir [9] or De Floriani and Magillo [11]. Recently, researchers have obtained a number of results on visibility addressing the watchtower problem and terrain guarding [2, 8]. The standard terrain model used in geometry is the polyhedral terrain, which is a continuous piecewise linear function defined over the triangles of a triangulation in

## There are no comments yet on this publication. Be the first to share your thoughts.