Convex Hull
Convex Hull
Convex Hull
Overview
The convex hull of a set of points is the smallest convex polygon that encloses all the points in the set. Imagine stretching a rubber band around the outermost points; the shape the rubber band takes is the convex hull. It is a fundamental concept in computational geometry with applications ranging from collision detection in computer graphics to pattern recognition and pathfinding.
Definition
Formally, the convex hull of a set of points S in a Euclidean space is the set of all convex combinations of its points. In 2D space, a polygon is convex if and only if any line segment connecting two points inside the polygon also lies completely inside it.
Key Concepts
Cross Product for Orientation
Many convex hull algorithms rely on the 2D cross product of three points p, q, and r to determine whether the turn from line segment pq to qr is counter-clockwise, clockwise, or collinear.
Jarvis March (Gift Wrapping)
The Jarvis March algorithm starts with the leftmost point (which is guaranteed to be on the hull). It then repeatedly selects the next point that is the most counter-clockwise relative to the current point until it returns to the starting point. Its time complexity is O(nh), where n is the total number of points and h is the number of points on the hull.
Graham Scan
Graham Scan finds the point with the lowest y-coordinate and sorts the remaining points by polar angle relative to this base point. It then processes the sorted points, using a stack to keep only those points that form a counter-clockwise turn. This algorithm runs in O(n log n) time due to the sorting step.
Divide and Conquer / Quickhull
Other popular algorithms include Divide and Conquer (splitting points into left and right halves and merging their hulls) and Quickhull (which borrows concepts from the Quicksort algorithm to recursively partition and process subsets of points). Both average O(n log n) time.
Historical Context
The problem of computing the convex hull is one of the oldest in computational geometry. Ronald Graham published the Graham Scan algorithm in 1972, originally to determine the convex hull of a finite set of points in the plane for applications in Bell Labs. R. A. Jarvis independently published the Gift Wrapping algorithm (Jarvis March) in 1973. Since then, it has become a standard introductory topic in algorithm design courses.
Applications
- Collision Detection: In video games and physics simulations, determining if complex shapes intersect is computationally expensive. Approximating objects with their convex hulls provides a fast preliminary check.
- Image Processing & Pattern Recognition: Convex hulls are used to analyze the shape of objects within an image, such as tracking hand gestures or recognizing characters.
- Geographic Information Systems (GIS): They help in computing the geographic boundary of a set of locations, like the area encompassing the spread of a disease outbreak.
- Robotics & Pathfinding: The convex hull of obstacles can simplify the environment model, aiding in efficient path planning for robots.
Related Concepts
- A* Pathfinding — path planning can be optimized using convex polygonal obstacle representation
- K-Means Clustering — clustering points geometrically often relates to evaluating their spatial boundaries
- Sorting Algorithms — algorithms like Graham Scan fundamentally rely on efficient sorting as a sub-routine
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive Convex Hull module.
Try Convex Hull on Riano →