ConcurrentHull: A Fast Parallel Computing Approach to the Convex Hull Problem

EasyChair Preprint 4480

Abstract

The convex hull problem has practical applications in mesh generation, file searching, cluster analysis, collision detection, image processing, statistics, etc. In this paper, we present a novel pruning-based approach for finding the convex hull set for 2D and 3D datasets using parallel algorithms. This approach, which is a combination of pruning, divide and conquer, and parallel computing, is flexible to be employed in a distributed computing environment. We propose the algorithm for both CPU and GPU (CUDA) computation models. The results show that ConcurrentHull has a performance gain as the input data size increases. Providing an independently dividable approach, our algorithm has the benefit of handling huge datasets as opposed to other approaches presented in this paper which failed to manage the same datasets.

Keyphrases: CUDA, convex hull, parallel algorithms, parallel computing

@booklet{EasyChair:4480,
  author    = {Sina Masnadi and Joseph J. LaViola Jr.},
  title     = {ConcurrentHull: A Fast Parallel Computing Approach to the Convex Hull Problem},
  howpublished = {EasyChair Preprint 4480},
  year      = {EasyChair, 2020}}