6267

A fast and robust seed flooding algorithm on GPU for Voronoi diagram generation

Licai Guo, Feng Wang, Zhangjin Huang, Naijie Gu
School of Computer Science and Technology, University of Science and Technology of China, Hefei, China
International Conference on Electrical and Control Engineering (ICECE), 2011

@article{xia2011accelerating,

   title={Accelerating Geospatial Analysis on GPUs using CUDA},

   author={XIA, Y. and KUANG, L. and LI, X.},

   year={2011}

}

Download Download (PDF)   View View   Source Source   

785

views

Voronoi diagram(VD) is a fundamental data structure in computational geometry. With the rapid development of programmable graphics programmable units, utilizing GPU to construct VD has been an optimal strategy. Considering the bridles of state-of-art algorithms, a seed flooding algorithm(SFA) is presented to achieve both robustness and high performance. The experimental results shows that SFA can construct exact discrete Voronoi diagrams with comparable performance of jump flooding algorithm(JFA), which is considered as the fastest approximate algorithm on GPU. The limitations of this algorithm are also analyzed and the schemes to alleviate the negative effect brought by bad inputs is presented.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: