Wenli Li and W. Randolph Franklin. GPU–accelerated multiple observer siting. Photogrammetric Engineering & Remote Sensing, 83(6):439–446, June 2017. doi:https://doi.org/10.14358/PERS.83.6.439.
[full text] [BibTeX▼]


We present two fast parallel implementations of the Franklin-Vogt multiple observer siting algorithm, using either OpenMP or CUDA. In this problem, the objective is to site observers on a raster terrain such that the joint area visible by them is maximized. On a terrain with 16385×16385 cells, assuming that observers can see out to a radius-of-interest of 100 cells, finding the approximately 15000 observers that have the greatest coverage takes only 17s in CUDA. That is a factor of 70 speedup from the sequential version. The OpenMP version exhibits a factor of 17 speedup on a 16 core system. Applications for the multiple observer siting problem include radio transmission towers, environmental monitoring sites, and path planning for surveillance drones. The algorithm has four steps: finding the visibility indices of all points, selecting a candidate subset of potential top observers, finding each one's viewshed, and greedily constructing the final solution.

Full Text

Your browser does not support viewing the PDF file inline. Please click the link below to download the file.