Document Type
Article
Language
eng
Publication Date
2019
Publisher
Institute of Electrical and Electronic Engineers (IEEE)
Source Publication
2019 IEEE 62nd International Midwest Symposium on Circuits and Systems
Source ISSN
0730-3157
Abstract
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.
Recommended Citation
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.
https://epublications.marquette.edu/comp_fac/16
Comments
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.