Divide-and-Conquer 3D Convex Hulls on the GPU

2012/05/06 by Jeffrey M. White, White, Jeffrey M., Kevin Wortman +2 · 5 citations
Computer Science · Engineering · Mathematics · #3D Shape Modeling and Analysis #Algorithm #Composite material #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Computer Graphics and Visualization Techniques #Computer graphics (images) #Computer science #Convex hull #D.1.3 #Distributed #Divide and conquer algorithms #FOS: Computer and information sciences #Geometry #Hull #I.3.5 #Materials science #Mathematics #Parallel #Parallel computing #Regular polygon #and Cluster Computing (cs.DC) #cs.CG #cs.DC

paper · pdf · doi:10.48550/arxiv.1205.1171

published in arXiv (Cornell University), 137-142 (Cornell University) · 11 pages, 9 figures

arxiv created 2012/05/06 · openalex publication_date 2012/05/06 · arxiv updated 2012/05/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

We describe a pure divide-and-conquer parallel algorithm for computing 3D convex hulls. We implement that algorithm on GPU hardware, and find a significant speedup over comparable CPU implementations.

Citations

• Convex hulls of finite sets of points in two and three dimensions
• The quickhull algorithm for convex hulls

Cited by

• gScan: Accelerating Graham Scan on the GPU
• CudaChain: an alternative algorithm for finding 2D convex hulls on the GPU

Related

• Finding Convex Hulls Using Quickhull on the GPU
• Accelerating the Convex Hull Computation with a Parallel GPU Algorithm
• A Straightforward Preprocessing Approach for Accelerating Convex Hull Computations on the GPU
• An Evaluation of GPU Filters for Accelerating the 2D Convex Hull
• CuClarabel: GPU Acceleration for a Conic Optimization Solver