Download PDFOpen PDF in browser

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

EasyChair Preprint 4480

12 pagesDate: October 27, 2020

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

BibTeX entry
BibTeX does not have the right entry for preprints. This is a hack for producing the correct reference:
@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}}
Download PDFOpen PDF in browser