Parallel geometric algorithms for multi-core computers. Research Report 6749

Computers with multiple processor cores using shared mem-ory are now ubiquitous. In this paper, we present several parallel geometric algorithms that specifically target this en-vironment, with the goal of exploiting the additional com-puting power. The d-dimensional algorithms we describe are (a) spatial sorting of points, as is typically used for pre-processing before using incremental algorithms, (b) kd-tree construction, (c) axis-aligned box intersection computation, and finally (d) bulk insertion of points in Delaunay triangu-lations for mesh generation algorithms or simply computing Delaunay triangulations. We show experimental results for these algorithms in 3D, using our implementations based on the Computational Geometry Algorithms Library (CGAL1). This work is a step towards what we hope will become a par-allel mode for CGAL, where algorithms automatically use the available parallel resources without requiring significant user intervention