Yi Zhuang '08

Computing visibility on terrains in external memory

Yi Zhuang In this project we consider the problem of computing visibility on very large grid terrains in external memory. Given an arbitrary viewpoint v, the visibility map (or viewshed) of v is the part the terrain that is visible from v. Visibility has numerous applications in GIS, ranging from path planning, navigation to placing towers.

We give an I/O-efficient algorithm for computing the viewshed of a point on a grid terrain and its experimental evaluation in external memory. Our algorithm is based on the grid interpolation model and line sweep algorithm proposed by Van Kreveld in internal memory and runs in O(sort(n)) IOs in the IO-model of Agarwal and Vitter. In practice our implementation clearly outperforms the previous (in- memory) algorithms and scales to very large datasets. It can compute the viewshed for terrains up to 4GB in a few hours on a desktop machine.