Friday, December 19, 2014

Parallelizable convex hull algorithm

Suppose you have a number of points in any number of dimensions, here I will just show 2.
First find the centroid, and the point farthest from that centroid Pc and construct the circle or n-dimensional sphere to it from the centroid... (Centroid shown in blue)
Now consider all the straight lines C to P(i) to B(i) from the Centroid to each Point and continuing on to a point on the Bounding region. Make a list of Pc and all points P(i) such that P(i) to B(i) is shorter than any other line from a different point P(j) to B(i).
This last step is the part that can be done in parallel, passing the entire set to as many processors as there are points and each one finding the solution for its given point. The points that are closest to their respective bounding point than any other point is to that bounding point are the hull. 

No comments:

Post a Comment