DocumentCode
1967114
Title
Computation of Voronoi diagrams using a graphics processing unit
Author
Majdandzic, Igor ; Trefftz, Christian ; Wolffe, Gregory
Author_Institution
Sch. of Comput., Grand Valley State Univ., Allendale, MI
fYear
2008
fDate
18-20 May 2008
Firstpage
437
Lastpage
441
Abstract
A parallel algorithm to compute a discrete approximation to the Voronoi diagram is presented. The algorithm, which executes in single instruction multiple data (SIMD) mode, was implemented on a high-end graphics processing unit (GPU) using NVIDIApsilas compute unified device architecture (CUDA) development environment. The performance of the resulting code is investigated and presented, and a mathematical model is developed that predicts the performance of the algorithm.
Keywords
approximation theory; computational geometry; computer graphic equipment; parallel algorithms; NVIDIA compute unified device architecture; SIMD; Voronoi diagram; discrete approximation; graphics processing unit; parallel algorithm; single instruction multiple data mode; Clocks; Concurrent computing; Graphics; Hardware; Parallel algorithms; Programming profession; Registers; Streaming media; Tiles; Yarn; GPGPU; Parallel Algorithms; SIMD; Voronoi;
fLanguage
English
Publisher
ieee
Conference_Titel
Electro/Information Technology, 2008. EIT 2008. IEEE International Conference on
Conference_Location
Ames, IA
Print_ISBN
978-1-4244-2029-2
Electronic_ISBN
978-1-4244-2030-8
Type
conf
DOI
10.1109/EIT.2008.4554342
Filename
4554342
Link To Document