Quickhull Algorithm for Convex Hull

Explanation

- **Quickhull Algorithm** is a divide and conquer approach for finding the convex hull of a set of points. It works by selecting the two extreme points (leftmost and rightmost), and then recursively dividing the set of points into two subsets (one on the left and one on the right) and finding the convex hull for each subset.

-

• Steps

  • Find the leftmost and rightmost points from the set of points.
  • Divide the points into two sets: one on the left of the line formed by the leftmost and rightmost points, and one on the right.
  • Recursively find the convex hull for each subset by finding the farthest point from the line and forming new sub-problems.
  • Combine the results to form the complete convex hull.

• Time Complexity

  • O(n log n) on average, where n is the number of points. However, in the worst case, it can be O(n²).