Convex Hull using Divide and Conquer Algorithm

Explanation

- **Convex Hull** is the smallest convex polygon that can enclose a set of points in a plane. The **Divide and Conquer Algorithm** for finding the Convex Hull works by dividing the set of points into smaller subsets, solving the Convex Hull problem for each subset, and then merging the results to form the final convex hull.

-

• Steps

  • Sort the points based on their x-coordinates (and y if necessary).
  • Divide the points into two halves.
  • Recursively compute the convex hull for each half of the set.
  • Merge the two convex hulls obtained from the two halves by finding the upper and lower tangent lines between the two hulls.
  • Return the combined convex hull.

• Time Complexity

  • Time complexity: O(n log n), where n is the number of points. The sorting step takes O(n log n), and merging takes linear time.