Skip to Main content Skip to Navigation
Conference papers

Parallel Geometric Algorithms for Multi-Core Computers

Abstract : Computers with multiple processor cores using shared memory are now ubiquitous. In this paper, we present several parallel geometric algorithms that specifically target this environment, with the goal of exploiting the additional computing power. The d-dimensional algorithms we describe are (a) spatial sorting of points, as is typically used for preprocessing before using incremental algorithms, (b) kd-tree construction, (c) axis-aligned box intersection computation, and finally (d) bulk insertion of points in Delaunay triangulations 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 (CGAL, http://www.cgal.org/). This work is a step towards what we hope will become a parallel mode for CGAL, where algorithms automatically use the available parallel resources without requiring significant user intervention.
Complete list of metadatas

Cited literature [28 references]  Display  Hide  Download

https://hal.inria.fr/inria-00409051
Contributor : Sylvain Pion <>
Submitted on : Wednesday, August 5, 2009 - 11:13:41 AM
Last modification on : Monday, October 19, 2020 - 2:34:02 PM
Long-term archiving on: : Monday, October 15, 2012 - 4:00:25 PM

File

parallel_cgal.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00409051, version 1

Collections

Citation

Vicente Batista, David Millman, Sylvain Pion, Johannes Singler. Parallel Geometric Algorithms for Multi-Core Computers. ACM Symposium on Computational Geometry, Jun 2009, Aarhus, Denmark. pp.217-226. ⟨inria-00409051⟩

Share

Metrics

Record views

377

Files downloads

670