Convex polygon algorithm in Cuda?

Question

I am searching for an algorithm to find a convex polygon to contain all the random points using Cuda. Is there anyone know a very efficient algorithm that I can adapt?

Answer 1

If you (or future SO users) are still looking for a 3D Hull algorithm for CUDA, you might check out this paper from November 2011:

"CudaHull: Fast Parallel 3D Convex Hull on the GPU" by Ayal Stein, Eran Geva, and Jihad El-Sana

http://www.cs.bgu.ac.il/~el-sana/publications/pdf/CudaHull.pdf

The authors claim a 27x to 40x speedup over Qhull (http://www.qhull.org) for 10 and 20 million points, respectively. For fewer points (< 10,000), though, their CPU / GPU algorithm is actually slower than Qhull.

I haven't implemented it myself, but came across both your SO question and the CudaHull paper when searching for 3D convex hull algorithms for CUDA.

Answer 2

There is a paper presented at HiPC about running a Convex Hull Algorithm on a GPU with CUDA.

Graham Scan is a simple algorithm to find the Convex Hull of a set of points. On the Wikipedia article exists a pseudo code version of it.