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.