The blurb

Improved Visibility Computations on Massive Grid Terrains
Jeremy Fishman and Laura Toma

Calculating visible points on grid or triangulated elevation maps is a computationally intensive task. A simplified nearest-neighbor interpolation for grid terrains equates to a Voronoi decomposition and permits a lower upper-bound on computation time. However, the well-known Van Kreveld algorithm under this simplification is still heavily I/O-bound on larger grids. We developed several much improved algorithms under the I/O model of Aggarwal and Vitter, including two cache-aware full visibility algorithms and one cache-oblivious approximation. Further work is focused on removing the Voronoi simplification in order to allow use of linear interpolations between grid points. A comparision of both interpolation models and the several I/O approaches can be performed using random viewpoints distributed among terrain features selected by flow modeling, and will allow us to quantify the trade-offs between computation time and accuracy on grids up to hundreds of gigabytes.