Convex Hull

Introduction: The “Rubber Band” Analogy

Hammer a bunch of nails into a board at random places. Now, take a rubber band and stretch it around all the nails, then let it snap tight. The shape formed by the rubber band is the Convex Hull. It is the boundary that encloses all points.

Finding this boundary efficiently is crucial in robotics, graphics, and image processing. The Graham Scan algorithm sorts the points angularly and builds the hull in one clean sweep.

What Problem does it solve?

• Input: A set of 2D points.
• Output: The subset of points that form the outermost polygon.
• The Promise: Simplifies a cloud of thousands of points into a simple polygon boundary.

Core Idea (Intuition)

1. Start Low: Find the bottom-most point (it must be part of the hull).
2. Sort by Angle: Sort all other points based on the angle they make with the start point.
3. Walk and Turn: Iterate through the sorted points.
   • If we turn Left, keep going.
   • If we turn Right (creating a dent), it means the previous point was inside the hull, not on the boundary. Remove the previous point.

Typical Business Scenarios

• ✅ Collision Detection: In games, instead of checking collisions against a complex 10,000-polygon character model, we check against its simple Convex Hull first.
• ✅ Robotics: A robot needs to know the “safe zone” around a group of obstacles to plan a path.
• ✅ Image Processing: Hand gesture recognition often involves finding the convex hull of the hand shape to count fingers (defects in the hull).
• ✅ GIS (Maps): “Find the area covered by these 50 delivery locations.”

Performance & Complexity

• Time: $O(N \log N)$ (dominated by sorting the points).
• Space: $O(N)$.

Summary

"The Convex Hull is the 'Shrink Wrap' of geometry. It simplifies a complex cloud of data into a clean, convex boundary, making calculations like collision and area much faster."