Convex Hull

A set of points is called convex if any two points in the set can be connected by a straight line that does not leave the set. For example, all regular polygons have convex interiors, but “bent” shapes or shapes with “holes” in them may not.

The convex hull of a set of points is the smallest convex set containing all of the points. In mathematical terms, the convex hull of any set S is the intersection of every convex set containing S. In the image below, if S is taken to be the set of points in the plane shown on the left, the convex hull of S is the filled set shown in the middle. Because we’re starting here from a finite set of points, the convex hull is always going to be a polygon whose vertices are a subset of our initial set S, so we also refer to the convex hull interchangably as just the boundary of that polygon, shown on the right.

Intuitively, the points are pegs sticking out of the plane, and the convex hull is the result of shrinking a giant rubber band around that set of points until it is tight.

Computing the convex hull

In a computational context, we’re given a list of n points in the plane as (x, y) pairs, and from this we need to calculate the convex hull: a polygon consisting of some of those points. We would also like to do it quickly, so we would prefer something better than O(n^2), or “for each point, examine every other point…”

By looking at the convex polygon above, we can quickly see some properties which will be true for all convex polygons:

• The leftmost and rightmost points are always part of the convex hull.
• Going anticlockwise, the junction made by three consecutive points is always a left turn.

These two observations are the core of the following algorithm for computing the convex hull:

• Sort the points from left to right.
• Initialise a new list to hold the hull computation.
• Going from left to right, add each point to the list. After adding each point, check that the last three points in the list make a left turn. If they don’t, the remove the second-last point.

This constructs the lower half of the hull. We can construct the upper half of the hull following the same idea, but going from right to left instead of from left to right. Then we join the two halves together (remembering to remove the duplicate end points).

The interactive example below uses the algorithm just described to compute the convex hull of any set of input points. While animating, large dots indicate dots which are part of the convex hull list being built, red indicates a right turn, and green indicates a left turn.

Click the visualisation to add more points.

The time complexity analysis for this algorithm is straightforward. Sorting points from left to right takes O(n \log n) time. Testing three points for whether or not they make a left or right turn takes constant time, and we do this a maximum of n times when building the bottom or halves of the hull. So the running time is dominated by the initial sort, and the time complexity of this algorithm is O(n \log n).

Further reading

• Show that the intersection of any collection of convex sets is convex.
• Show that the union of two convex sets may not be convex. Hint: Use induction on the size of S.
• Let V be any vector space over \mathbb{R}, and S = \{v_1, v_2, \ldots, v_n\} be a finite set of vectors from V. The sum \sum \lambda_i v_i is called a convex combination if 0 \leq \lambda_i \leq 1 for all i, and \sum \lambda_i = 1.
• Show that the set of all convex combinations of S is equal to the convex hull of S.}
• Let V be a Banach space (a complete normed vector space over \mathbb{R} or \mathbb{C}), and S \subseteq V be convex. Show that the closure of S is convex.