Chaulio R. Ferreira, Marcus V. A. Andrade, Salles V. G. Magalhães, W. R. Franklin, and Guilherme C. Pena.
A parallel sweep line algorithm for visibility computation.
In Geoinfo 2013, XIV Brazilian Symposium on GeoInformatics. Campos do Jordão, SP, Brazil, 24–27 Nov 2013.
Winner of best paper award, \url http://www.geoinfo.info/geoinfo2013/index.php.
[full text] [BibTeX▼]
This paper describes a new parallel raster terrain visibility (or viewshed) algorithm, based on the sweep-line model of [Van Kreveld 1996]. Computing the terrain visible from a given observer is required for many GIS applications, with applications ranging from radio tower siting to aesthetics. Processing the newly available higher resolution terrain data requires faster architectures and algorithms. Since the main improvements on modern processors come from multi-core architectures, parallel programming provides a promising means for developing faster algorithms. Our algorithm uses the economical and widely available shared memory model with OpenMP. Experimentally, our parallel speedup is almost linear. On 16 parallel processors, our algorithm is up to 12 times faster than the serial implementation.