A Parallel Algorithm for Viewshed Computation on Grid Terrains

Abstract

Viewshed (or visibility map) computation is an important component in many GIS applications and, as nowadays there are huge volume of terrain data available at high resolutions, it is important to develop efficient algorithms to process these data. Since the main improvements on modern processors come from multi-core architectures, parallel programming provides a promising means for developing faster algorithms. In this paper, we describe a new parallel algorithm based on the model proposed by [Van Kreveld 1996]. Our algorithm uses the shared memory model, which is relatively cheap and supported by most current processors.Experiments have shown that, with 16 parallel cores, it was up to 12 times faster than the serial implementation, and up to 3.9 times using four parallel cores, which is an almost optimal speedup.