Adding the Quickhull algorithm to find Convex Hull

This is a(n):

• [ Yes] New algorithm
• Update to an existing algorithm
• Error
• Proposal to the Repository

Details:

The QuickHull algorithm is a Divide and Conquer algorithm similar to QuickSort. Let a[0…n-1] be the input array of points. Following are the steps for finding the convex hull of these points.

1. Find the point with minimum x-coordinate lets say, min_x and similarly the point with maximum x-coordinate, max_x. Make a line joining these two points, say L. This line will divide the whole set into two parts. Take both the parts one by one and proceed further.

2. For a part, find the point P with maximum distance from the line L. P forms a triangle with the points min_x, max_x. It is clear that the points residing inside this triangle can never be the part of convex hull.

3. The above step divides the problem into two sub-problems (solved recursively). Now the line joining the points P and min_x and the line joining the points P and max_x are new lines and the points residing outside the triangle is the set of points.

4. Repeat point no. 3 till there no point left with the line. Add the end points of this point to the convex hull.