Institute of Electrical and Electronic Engineers (IEEE)
2019 IEEE 62nd International Midwest Symposium on Circuits and Systems
Voronoi diagram construction is a common and fundamental problem in computational geometry and spatial computing. Numerous sequential and parallel algorithms for Voronoi diagram construction exists in literature. This paper presents a multi-threaded approach where we augment an existing sequential implementation of Fortune's planesweep algorithm with compiler directives. The novelty of our fine-grained parallel algorithm lies in exploiting the concurrency available at each event point encountered during the algorithm. On the Intel Xeon E5 CPU, our shared-memory parallelization with OpenMP achieves around 2x speedup compared to the sequential implementation using datasets containing 2k-128k sites.
Paudel, Anmol; Yang, Jie; and Puri, Satish, "Parallelization of Plane Sweep Based Voronoi Construction with Compiler Directives" (2019). Computer Science Faculty Research and Publications. 16.
ADA Accessible Version
Accepted version. 2019 IEEE 62nd International Midwest Symposium on Circuits and Systems, (2019): 908-911. DOI. © 2019 Institute of Electrical and Electronic Engineers (IEEE). Used with permission.