📐 Convex Hull Foundations

🎯 What is a Convex Hull?

The convex hull of a set of points is the smallest convex polygon that contains all points. It's fundamental to computational geometry.

Core Concepts

Convex set: Any line segment between points in the set is also in the set. Extreme points: Vertices of the hull. Application: Collision detection, pattern recognition.

📌 Convex📌 Extreme Points📌 Smallest Set

def cross(o, a, b):
    """Cross product of vectors OA and OB"""
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

def distance(p1, p2):
    """Euclidean distance between two points"""
    return ((p2[0] - p1[0])**2 + (p2[1] - p1[1])**2)**0.5

📐 Graham Scan Algorithm

🎯 Classic O(n log n) Algorithm

Graham scan sorts points by polar angle and uses a stack to build the convex hull in O(n log n) time.

Algorithm Steps

Find lowest point: Pivot with minimum y. Sort: By polar angle from pivot. Scan: Use stack to remove non-left turns.

📐 O(n log n)📊 Stack🔄 Left Turns

def graham_scan(points):
    """Graham scan convex hull algorithm"""
    if len(points) <= 3:
        return points
    
    # Find lowest point
    pivot = min(points, key=lambda p: (p[1], p[0]))
    
    # Sort by polar angle
    sorted_points = sorted(points, key=lambda p: (atan2(p[1]-pivot[1], p[0]-pivot[0]), distance(pivot, p)))
    
    # Build hull with stack
    hull = []
    for p in sorted_points:
        while len(hull) >= 2 and cross(hull[-2], hull[-1], p) <= 0:
            hull.pop()
        hull.append(p)
    
    return hull

✖️ Cross Product

🎯 Geometric Predicate

Cross product determines if three points make a left turn (counter-clockwise), right turn, or are collinear.

Cross Product Uses

Orientation: Positive = CCW, Negative = CW, Zero = Collinear. Convexity: All left turns for convex hull. Point-in-polygon: Using winding number.

✖️ Orientation🔄 CCW/CW📐 Collinear

def orientation(p, q, r):
    """Return orientation of (p,q,r)"""
    val = (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])
    if val > 0:
        return 1  # Counter-clockwise
    elif val < 0:
        return -1  # Clockwise
    else:
        return 0  # Collinear

📊 Sorting by Angle

🎯 Polar Angle Sorting

Sort points by the angle they make with the pivot point. This is the key to Graham scan's efficiency.

Angle Calculation

Atan2: Compute angle using atan2(dy, dx). Comparator: Sort by angle, then distance. Stability: O(n log n) comparison sort.

📊 Angle📐 Atan2📈 O(n log n)

def polar_angle(p, q):
    """Compute polar angle from p to q"""
    return math.atan2(q[1] - p[1], q[0] - p[0])

def sort_by_polar(points, pivot):
    """Sort points by polar angle from pivot"""
    return sorted(points, key=lambda p: (polar_angle(pivot, p), distance(pivot, p)))

📚 Stack Operations

🎯 Maintaining the Hull

The stack keeps track of hull vertices. Points that create right turns are popped from the stack.

Stack Logic

Push: Add point to stack. Pop: Remove point when right turn detected. Invariant: Stack always contains convex chain.

📚 Push📚 Pop🔄 Invariant

def build_hull(points):
    """Build convex hull using stack"""
    hull = []
    for p in points:
        while len(hull) >= 2:
            if cross(hull[-2], hull[-1], p) > 0:
                break
            hull.pop()
        hull.append(p)
    return hull

📊 Monotone Chain

🎯 Andrew's Algorithm

Monotone chain is a variant of Graham scan that sorts by x-coordinate and builds upper and lower hulls.

Monotone Chain Steps

Sort by x: Then y for ties. Lower hull: Left to right. Upper hull: Right to left. Combine: Merge both hulls.

📊 O(n log n)📐 Upper/Lower🔄 Merge

def monotone_chain(points):
    """Monotone chain convex hull algorithm"""
    points = sorted(points)
    if len(points) <= 1:
        return points
    
    # Lower hull
    lower = []
    for p in points:
        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
            lower.pop()
        lower.append(p)
    
    # Upper hull
    upper = []
    for p in reversed(points):
        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)
    
    return lower[:-1] + upper[:-1]

🔄 Jarvis March

🎯 Gift Wrapping

Jarvis march (gift wrapping) finds convex hull by wrapping a string around the points. O(nh) where h is hull size.

March Steps

Start: Leftmost point. Wrap: Find point with minimum angle. Repeat: Until back to start.

🔄 O(nh)📊 Wrapping🔁 Iterative

def jarvis_march(points):
    """Jarvis march (gift wrapping) algorithm"""
    if len(points) <= 3:
        return points
    
    hull = []
    start = min(points)
    current = start
    
    while True:
        hull.append(current)
        next_point = points[0]
        for p in points:
            if p == current:
                continue
            if orientation(current, next_point, p) == -1:
                next_point = p
            elif orientation(current, next_point, p) == 0:
                if distance(current, p) > distance(current, next_point):
                    next_point = p
        current = next_point
        if current == start:
            break
    
    return hull

⚡ QuickHull

🎯 Divide and Conquer

QuickHull recursively finds extreme points, similar to quicksort. Expected O(n log n), worst-case O(n²).

QuickHull Steps

Find extremes: Min/max x. Partition: Points on left and right. Recur: Find hull recursively.

⚡ O(n log n)📊 Recursive🔄 Divide

def quickhull(points):
    """QuickHull algorithm for convex hull"""
    if len(points) <= 1:
        return points
    
    # Find extreme points
    left = min(points, key=lambda p: p[0])
    right = max(points, key=lambda p: p[0])
    
    # Partition points
    left_set = []
    right_set = []
    for p in points:
        if p == left or p == right:
            continue
        if orientation(left, right, p) > 0:
            left_set.append(p)
        else:
            right_set.append(p)
    
    # Find hull recursively
    hull = [left]
    hull.extend(find_hull(left_set, left, right))
    hull.append(right)
    hull.extend(find_hull(right_set, right, left))
    
    return hull

📊 Divide & Conquer

🎯 Optimal O(n log n)

Divide and conquer splits points, computes hulls, and merges them. Guaranteed O(n log n) worst-case.

Merge Process

Split: Divide by x-coordinate. Conquer: Compute hulls recursively. Merge: Find common tangents.

📊 O(n log n)📐 Merge🔄 Tangents

def divide_conquer_hull(points):
    """Divide and conquer convex hull"""
    if len(points) <= 5:
        return graham_scan(points)
    
    # Divide by x-coordinate
    mid = len(points) // 2
    left = divide_conquer_hull(points[:mid])
    right = divide_conquer_hull(points[mid:])
    
    # Merge hulls
    return merge_hulls(left, right)

📈 Complexity Analysis

🎯 Time and Space

Graham scan: O(n log n) time, O(n) space. Optimal for convex hull in 2D.

Complexity Comparison

Graham Scan: O(n log n). Jarvis March: O(nh). QuickHull: O(n log n) expected. Divide & Conquer: O(n log n).

📈 O(n log n)📊 Space O(n)⚡ Optimal

# Complexity analysis
# n = number of input points
# h = number of hull vertices

complexities = {
    "Graham Scan": "O(n log n) time, O(n) space",
    "Jarvis March": "O(nh) time, O(n) space",
    "QuickHull": "O(n log n) expected, O(n²) worst",
    "Divide & Conquer": "O(n log n) time, O(n) space"
}

🚀 Applications

🎯 Real-World Uses

Convex hull algorithms are used in computer graphics, robotics, pattern recognition, and geographic information systems.

Application Domains

Collision detection: Bounding volumes. Image processing: Shape analysis. Robotics: Path planning. GIS: Boundary detection.

🎨 Graphics🤖 Robotics📊 GIS

class BoundingVolume:
    def __init__(self, points):
        self.hull = graham_scan(points)
    
    def intersects(self, other):
        # Check if hulls intersect
        for p in self.hull:
            if point_in_polygon(p, other.hull):
                return True
        return False

🔧 Variants & Extensions

🎯 Specialized Algorithms

Variants handle special cases: parallel processing, 3D hulls, online algorithms, and approximate hulls.

Extension Types

3D hull: Convex hull in 3D. Online: Dynamic point insertion. Approximate: Trade accuracy for speed.

🔧 3D📊 Online📈 Approx

def approximate_hull(points, epsilon):
    """Approximate convex hull with error tolerance"""
    # Reduce points using Ramer-Douglas-Peucker
    simplified = rdp(points, epsilon)
    return graham_scan(simplified)

👁️ Visualization

🎯 Understanding the Algorithm

Visualizing the hull algorithm helps understand the process and identify edge cases.

Visualization Tools

Matplotlib: Plot points and hull. Animation: Show steps of algorithm. Interactive: Click to add/remove points.

👁️ Plot🔄 Animate🖱️ Interactive

def visualize_hull(points, hull):
    """Visualize points and convex hull using matplotlib"""
    import matplotlib.pyplot as plt
    
    # Plot points
    plt.scatter(*zip(*points), color='blue', label='Points')
    
    # Plot hull
    hull_points = hull + [hull[0]]
    plt.plot(*zip(*hull_points), color='red', label='Hull')
    
    plt.legend()
    plt.show()

🔬 Advanced Topics

🎯 Research Frontiers

Current research includes streaming algorithms, distributed convex hull, and quantum algorithms.

Research Directions

Streaming: Process points in one pass. Distributed: Parallel hull computation. Quantum: Quantum algorithms for hull.

🔬 Streaming📊 Distributed⚛️ Quantum

def streaming_hull(points_stream):
    """Online convex hull for streaming data"""
    hull = []
    for p in points_stream:
        hull.append(p)
        if len(hull) > 3:
            hull = graham_scan(hull)
    return hull