Convex Hull
Authors: Benjamin Qi, Neo Wang
Prerequisites
Smallest convex polygon containing a set of points on a grid.
Introduction
The Convex Hull is the subset of points that forms the smallest convex polygon which encloses all points in the set. To visualize this, imagine that each point is a pole. Then, imagine what happens if you were to wrap a rope around the outside of all the poles, and then pull infinitely hard, such that the connections between any two points that lie on the edge of the rope are lines. The set of points that touch the rope is the convex hull.
Convex Hull Visualization
Focus Problem – read through this problem before continuing!
With Graham Scan
Resources | |||
---|---|---|---|
Wikipedia | |||
VisuAlgo | |||
UCSD |
Solution
Resources | |||
---|---|---|---|
Benq |
C++
The Graham Scan algorithm works in 3 steps. First, it sorts all of the points by their counterclockwise angle around a pivot , breaking ties by distance. This algorithm uses the leftmost (and bottommost if there is a tie), point as .
We maintain a stack containing the points such that the following invariant holds: every three consecutive points of the stack form a counterclockwise turn. In other words, lies to the left of the line from to . This condition implies that the points of the stack form the vertices of a convex polygon.
To start the creation of the convex hull, we choose 2 points. The pivot (first point), and the second point based on our initial sorting. After that, we attempt to add each point in to the stack.
Denote our stack as , the top element of as and as the -th sorted candidate point. Before adding to the stack, we check whether forms a counterclockwise turn.
- If so, then we add to the stack and the invariant holds. Continue with .
- Otherwise, lies within the convex hull of the other points in the stack along with , so we pop from the stack and continue with .
Illustration
Worked Example
#include <bits/stdc++.h>using namespace std;#define FOR(i, a, b) for (int i = (a); i < (b); i++)#define FORE(i, a, b) for (int i = (a); i <= (b); i++)#define F0R(i, a) for (int i = 0; i < (a); i++)#define trav(a, x) for (auto &a : x)#define f first
With Monotone Chain
Resources | |||
---|---|---|---|
CPH | |||
Wikipedia | |||
Benq |
Solution
This section is not complete.
Rotating Caliphers
Focus Problem – read through this problem before continuing!
Solution
Resources | |||
---|---|---|---|
CF |
This section is not complete.
Problems
Status | Source | Problem Name | Difficulty | Tags | |||||
---|---|---|---|---|---|---|---|---|---|
CF | Easy | Show TagsConvex | |||||||
Plat | Normal | Show TagsConvex | |||||||
CF | Normal | Show TagsConvex, PURS | |||||||
Old Gold | Normal | Show TagsConvex | |||||||
Kattis | Hard | Show TagsConvex | |||||||
AC | Very Hard | Show TagsConvex | |||||||
Module Progress:
Join the USACO Forum!
Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!