Drag the points!
Introduction
Given a set of points, what is the smallest convex shape that encloses all of them? What is the boundary of this shape?
This is the convex hull problem.
2D Convex Hull
Observations
Notice that given a convex hull, all points lie on the same side of every edge.
Observe that for every edge, all points lie on the same side (right for top and bottom; left for all other).
Idea 1: Add Edges with All Points on the same side
Naive Algorithm
$$ \begin{align*} &\texttt{bool allPointsOnSameSideOf($e$):}\newline &\texttt{\qquad for all other points $p\not\in e$:}\newline &\texttt{\qquad \qquad if any $p$ on different side of $e$:}\newline &\texttt{\qquad \qquad \qquad return false}\newline &\texttt{\qquad return true}\newline &\newline &\texttt{for all points $p1$:}\newline &\texttt{\qquad for all other points $p2$:}\newline &\texttt{\qquad \qquad consider edge $e$ = ($p1$, $p2$)}\newline &\texttt{\qquad \qquad if allPointsOnSameSideOf($e$):}\newline &\texttt{\qquad \qquad \qquad add $e$ to convex hull}\newline \end{align*} $$
Checking if all points are on the same side is a linear ($\mathcal{O}(n)$) operation. Iterating through all possible edges is a quadratic operation ($\mathcal{O}(n^2)$). Thus, this algorithm has cubic time complexity ($\mathcal{O}(n^3)$).
Observation
We are checking all possible edges, but really edges are contiguous on a hull ($A\rightarrow B\rightarrow C\rightarrow A$ like a chain).
But what about the first edge? Here’s another observation: the convex hull must contain the leftmost ($\min_x$) point!
If there are multiple leftmost points, then they must all be on the convex hull. Otherwise, that point would not be contained in the convex hull.
With this chain in mind, we shouldn’t be iterating over all points for the next: in a chain, the next point should be “close” to the current pivot point. Could we precompute with a sort in some way?
Graham Scan
Algorithm
$$ \begin{align*} &\texttt{let hull = [$\min_x$]}\newline &\texttt{sort all points by $\theta$ with $\min_x$}\newline &\newline &\texttt{for all points $p\neq\min_x$:}\newline &\texttt{\qquad add $p$ to hull}\newline &\texttt{\qquad while hull (with $p$) is no longer convex:}\newline &\texttt{\qquad \qquad pop hull}\newline \end{align*} $$ Convex meaning that the hull only “leans” in one direction (always curving left OR always curving right). This can easily be checked by verifying that the current point $p$ is on the same side of the previous edge (or vacuously true if there is no previous edge).
Example
Here, the leftmost point is highlighted in red. We sort the other points by their angle with this point (ordered numbering).
After a few iterations, our hull is still convex (always left leaning).
Now, the hull’s convexitivity breaks.
Still broken (we only have to check that the current red point is on the left side of the 2nd-to-last edge).
Convex!
If we continue the algorithm, we will eventually reach the full convex hull.
Analysis
Determining the leftmost point just requires a linear scan ($\mathcal{O}(n)$). Since determining the angle between two points takes constant time ($\mathcal{O}(1)$), the initial sort has the normal time complexity $\mathcal{O}(n \log n)$.
Every point will be the current point (red dot in example) exactly once, so this iteration has linear time complexity ($\mathcal{O}(n)$).
What about popping non-convex points? Observe that any point can be popped at most once! So it has linear time complexity ($\mathcal{O}(n)$).
$$\mathcal{O}(n) + \mathcal{O}(n \log n) + \mathcal{O}(n) + \mathcal{O}(n)$$ $$\subseteq\mathcal{O}(n \log n)$$
A bit of notation abuse, but I think the point still gets across.
Above and Beyond
Anything in this section serves as very light introductions to convex hull extensions. You should treat them as just introductions and feel free to explore further beyond this blog post.
There are various algorithms for solving this problem in $d$-dimensions. For the 3D problem, there exists a deterministic divide-and-conquer $\mathcal{O}(n \log n)$ algorithm (but is notoriously difficult, especially the merge step).
Chan’s Algorithm
Chan’s algorithm is an output-sensitive algorithm for calculating the convex hull in 2D and 3D space.
It relies on existing $\mathcal{O}(n \log n)$ algorithms in those spaces (Graham Scan, divide-and-conquer, etc.) and uses them to solve subpartitions of the original point set. It then combines these mini-convex hulls to solve the full problem.
It has time complexity $\mathcal{O}(n \log h)$, where $h$ is the number of vertices in the solution convex hull.
Quick Hull
For the general $d$, Quick Hull is a Las Vegas algorithm that has a time complexity of $\mathcal{O}(n \log n)$ in expectation for the 2D and 3D case.
The $d$-dimensional generalization adds a time complexity factor of $n^{\lfloor\frac{d}{2}\rfloor}$. I don’t have great intuition on this expression, but it has to do with the number of facets on a $d$-dimensional object (increasing recursion breadth).
I don’t have great exposure to Quick Hull, but the general idea is that we begin with a “starter hull” (subset of the convex hull; encompasses a large percentage of points in expectation).
For the 2D case, this hull might have $p_1=\min_x$, $p_2=\max_x$, and $p_3=\max_\text{dist}(p_1p_2)$ (the point that is furthest from the line $p_1p_2$).
For the 3D case, this hull might have the same points as in the 2D case plus $p_4=\max_\text{dist}(p_1p_2p_3)$ (the point that is furthest from the plane $p_1p_2p_3$)
Then, for each facet on the current hull (line in 2D; plane in 3D), add the point $p$ (on the other side of the hull) farthest from the facet.
This inclusion may break the convexitivity of the current hull. Perform BFS to determine the “horizon” of $p$ and remove all visited points not in the horizon.
The horizon is what you might be able to see if you were to put your eye at $p$. This can be checked using linear algebra magic.
If you can see a point $a$ behind a point $b$, then that means $b$ is not in the horizon and causes the hull to be concave.
Recursively repeat the previous two steps until every point is enclosed in the hull.