This note is about the convex hull, which it says shows up often in competitive programming exercises. Given points on the Oxy plane, the hull is the smallest convex set that contains all of them. The note also calls that set the smallest polygon around the points. The picture in the note is a rubber band pulled tight around nails. The algorithms named for computing it are Graham and Monotone Chain.
Convex Hull
The convex hull is a problem that appears very frequently in computational geometry exercises in competitive programming.
Given a set of points on the Oxy coordinate plane, the convex hull of the set is the smallest convex set (in terms of area, volume, etc.) that contains all of those points. In other words, the convex hull of a point set is the smallest polygon that contains all the points.
Intuitively, if each point is a nail hammered into a wooden board, the outline of the convex hull is a rubber band stretched tight around the nails on all sides.
Common Convex Hull Algorithms
- Graham
- Monotone Chain
See also: Problem Solving Approaches · Learning Resources