Convex Hull Problem

Here is the Convex Hull problem.

• Definition: Given a finite set of points \(S\) in the plane, the convex hull is the smallest convex polygon that contains all points in \(S\).
• Formalization:
  • A convex set is one where, for any two points inside it, the line segment connecting them is also inside.
  • The convex hull of \(S\), denoted \(\text{CH}(S)\), is the intersection of all convex sets containing \(S\).

Here is an intuitive way to think about it: imagine stretching a rubber band around the set of points; when released, it snaps to the convex hull.

Naive Algorithm (Brute Force)

Idea

Check every pair of points to see if they form an edge of the convex hull.

Steps

1. For each pair of points \((p_i, p_j)\):
   • Consider the line through them.
   • Check whether all other points lie on one side of the line (or on the line itself).
2. If true, then \((p_i, p_j)\) is an edge of the convex hull.
3. Collect all such edges and order them to form the polygon.

Complexity

• Time: \(O(n^3)\) (since for each of the \(O(n^2)\) pairs, we check \(O(n)\) points).
• Space: \(O(n)\).

This is extremely inefficient. How can we do better?

Divide and Conquer Algorithm

Idea

Split the set of points into halves, compute convex hulls recursively, and merge them.

Steps

1. Sort points by x-coordinate.
2. Divide into two halves: left and right.
3. Recursively compute convex hulls for each half.
4. Merge step:
   • Find the upper and lower tangents between the two hulls.
   • Combine them to form the overall convex hull.

The merge step is the key stroke of genius in this algorithm:

MERGE(leftHull, rightHull):
    # Step 1: Find the rightmost point of leftHull and leftmost point of rightHull
    pL = rightmost_point(leftHull)
    pR = leftmost_point(rightHull)

    # Step 2: Find upper tangent
    while not is_upper_tangent(pL, pR, leftHull, rightHull):
        if slope(pL, pR) < slope(next_point(leftHull, pL), pR):
            pL = next_point(leftHull, pL)
        else:
            pR = prev_point(rightHull, pR)

    upperL = pL
    upperR = pR

    # Step 3: Find lower tangent
    pL = rightmost_point(leftHull)
    pR = leftmost_point(rightHull)
    while not is_lower_tangent(pL, pR, leftHull, rightHull):
        if slope(pL, pR) > slope(prev_point(leftHull, pL), pR):
            pL = prev_point(leftHull, pL)
        else:
            pR = next_point(rightHull, pR)

    lowerL = pL
    lowerR = pR

    # Step 4: Construct merged hull
    mergedHull = points_between(upperL, lowerL, leftHull) +
                 points_between(lowerR, upperR, rightHull)

    return mergedHull

Here, the merge step takes worst case \(O(n)\) which leads to the merge sort recurrence. Even with binary search, we will still have the same complexity.

Complexity

• Time: \(O(n \log n)\).
• Space: \(O(n)\).

Convex Hull Trick

Refer to https://cp-algorithms.com/geometry/convex_hull_trick.html