Parallel Voronoi Diagram computation on scaled distance planes using CUDA

Julio Toss, Joao Comba
Institute of Informatics – Federal University of Rio Grande do Sul (UFRGS), Av. Bento Gonalves 9500, Porto Alegre – RS – Brasil
11th Workshop on Parallel and Distributed Processing (WSPPD), 2013


   title={Parallel Voronoi Diagram computation on scaled distance planes using CUDA},

   author={Toss, Julio and Comba, Joao},



Download Download (PDF)   View View   Source Source   



Voronoi diagrams are fundamental data structures in computational geometry with several applications on different fields inside and outside computer science. This paper shows a CUDA algorithm to compute Voronoi diagrams on a 2D image where the distance between points cannot be directly computed in the euclidean plane. The proposed method extends an existing Dijkstra-based GPU algorithm to treat our 2D images as graph and then compute the shortest-paths to create each Voronoi cell. Experimental results report speed-ups up to almost 40x over current reference sequential method for Voronoi computation on non-euclidean space. This problem is a building block of the deformation engine in the SOFA physics simulation framework.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: