Improved visibility computation on massive grid terrains

This paper describes the design and engineering of algorithms for computing visibility maps on massive grid terrains. Given a terrain T, specified by the elevations of points in a regular grid, and given a viewpoint v, the visibility map or viewshed of v is the set of grid points of T that are visible from v. We describe three new algorithms to compute the viewshed for any given terrain T and viewpoint v. The first two algorithms "sweep" the terrain by rotating a ray around the viewpoint while maintaining the terrain profile along the ray. On a terrain of n grid points, these algorithms run in O(n log n) time and O(sort(n)) I/Os in the I/O-model of Aggarwal and Vitter. The difference between the two algorithms is in the preprocessing before the sweep: the first algorithm sorts the grid points into concentric bands around the viewpoint; the second algorithm sorts the grid points into sectors around the viewpoint. The third algorithm sweeps the terrain centrifugally, growing a star-shaped region around the viewpoint while maintaining the approximate visible horizon of the terrain within the swept region. This algorithm runs in O(n) time and O(scan(n)) I/Os and is cache-oblivious. We tested our algorithms on NASA SRTM data, and found that our fastest new algorithm computes the viewshed of a terrain of 7.6 billion points (28.4 GiB) in 203 minutes on a machine with 0.5 GiB RAM and a laptop-speed hard drive. Depending on the data set, the new algorithm is 20 to 50 times faster than the algorithm from our previous work.