Definition

Let \( X \) be a set of points in \( \mathbb{R}^{k} \). The convex hull of \( X \) is the smallest convex set that contains all points in \( X \).
If \( X \) is finite, then the convex hull of \( X \) is a \( k \)-polytope.
In the finite, \( \mathbb{R}^{2} \) case, the convex hull of \( X \) is a convex polygon.
In the finite case, the convex hull of \( X \) can be also defined as the set of all the convex combinations of the points of \( X \): \[ \mathrm{ConvexHull}(X) = \left\{\left.\sum_{i=1}^{|X|} \alpha_i x_i \right| (\forall i:\ \alpha_i \ge 0) \wedge \sum_{i=1}^{|X|} \alpha_i = 1 \right\} \]

Applications

Finding the convex hull of a set of points is useful in all kinds of fields, most notably: Given that the amount of points of which we want to find the convex hull can be very large, it is important not only that we have correct ways of finding it, but also that they're fast.
In this document the Bachmann–Landau notation will be used to describe the computational complexity of the presented algorithms.

Algorithms

Optimal algorithms for finding the convex hull exist for the \( \mathbb{R}^{2} \) and \( \mathbb{R}^{3} \) cases. In this context "optimal" means an algorithm that takes \( O(kn\log{h}) \) steps, where \( n := |X| \), \( h \) is the number of vertices in the convex hull (it is determined after the algorithm has found the convex hull) and \( k \) is the number of dimensions.
Even if optimal algorithms exist, generally is enough to have an efficient algorithm, one that takes \( O(k^{d}n\log{n}) \) where \( d \) is some fixed number in \( \mathbb{R}_0^{+} \).
We will focus on the \( \mathbb{R}^{2} \) case, but some of the presented algorithms are trivally generalizable to higher dimensions.

Naïve

Since \( X \) is finite, the convex set of \( X \) is a polygon. We want to find its edges; to do that, we try all possible edges, and test whether all points lie exactly in one of the semi-planes defined by that edge: if it's true, then that edge is part of the convex hull.


This algorithm takes \( \Theta(n^{3}) \) steps in the \( \mathbb{R}^{2} \) case.
It can be easily generalized to the \( \mathbb{R}^{k} \) case, taking \( \Theta(kn^{k + 1}) \) steps.
A smarter version of this algorithm breaks the innermost loop as soon as two points on opposing sides of the line are found.

Gift Wrapping

This algorithm was independently created by Chand & Kapur (1970) and by R. A. Jarvis (1973).
The algorithm starts by picking a point known to be on the convex hull: it can be the lowest, the highest, the rightmost or the leftmost. Then it selects the next point such that all other points lie in the right semiplane defined by the line passing through those two points. It then repeats the process starting from the last point until it reaches the starting point.


This algorithm takes \( \Theta(nh) \) steps in the \( \mathbb{R}^{2} \) case.

QuickHull

This algorithm was independently created by W. Eddy (1977) and by A. Bykat (1978).
The algorithm works in two phases:
  1. Splits the input in 2 sets separated by a line
  2. Recursively excludes point from the convex hull
In the first phase the algorithm selects two points known to be in the convex hull (two of the lowest, the highest, the rightmost and the leftmost). Then, it separates the points that lie on opposite sides of the line passing through the two previously selected points. It then calls the second phase on those two sets.
In the second phase the algorithm takes a segment and some points all on one side of this line. It finds the furthest point from the line, creates a triangle with that point and the given segment and categorize points: if a point is inside the triangle, it gets discarded; the other points are grouped according to the side of the triangle they're on and the second phase it's recursively called on those two groups of points. If one side (excluding the given segment) has no points on it, it becomes part of the convex hull.


This algorithm takes \( O(n^{2}) \) steps in the \( \mathbb{R}^{2} \) case.
If we're lucky that the splits always divide the points in two almost equally sized sets, the algorithm takes \( \Omega(n \log{n}) \) steps.
It can be generalized for the \( \mathbb{R}^{k} \) case, taking \( O(k^{2} n^{2}) \) steps in the worst case and \( \Omega(k^{2} n \log{n}) \) steps if we're lucky.

Monotone Chain

This algorithm was created by A. M. Andrew (1979).
The algorithm first sorts the points in lexicographic ascending order. Then it builds the lower and upper convex hulls in the following way: starting from the first point (the last for the upper side) it continues to add points in order until there is a right turn. When a right turn is detected, it removes the last point that is part of the convex hull until there are only left turns.


This algorithm takes \( O(n \log{n}) \) steps in the \( \mathbb{R}^{2} \) case.
The number of steps is dominated by the sort operation, which takes \( O(n \log{n}) \) steps, while the remaining part of the algorithm takes \( \Theta(n) \) steps.

Kirkpatrick-Seidel

This algorithm was created by David G. Kirkpatrick and Raimund Seidel (1983).
The algorithm should do something like the following: First find a vertical line that divides the given point set in two approximately equal sized parts. Next determine the "bridge" crossing this line, i.e. the edge of the upper hull that intersects this line. Eliminate the points that lie underneath the bridge, and finally apply the algorithm recursively to the two sets of the remaining points on the left and right side of the vertical line. The only difficult part in such an algorithm appears to be the construction of the bridge. Finding the bridge in linear time: We are given a set S of n points in the plane and a vertical line L which has points of S to its left and right. We are to find the edge of the upper hull of S that intersects L. If two edges intersect L, i.e. L contains a vertex v of the upper hull, we want to identify the edge for which v is the left endpoint. Call this edge the bridge and its endpoints bridge points. Let us define a supporting line of S to be a nonvertical straight line which contains at least one point of S but has no points of S above it. Obviously the bridge must be contained in some supporting line. Call this line b and let Sb be the slope of b. For our purposes, finding the bridge means identifying the two bridge points. One possible way of achieving this is to successively eliminate points from S as candidates for bridge points. For this purpose we pair up the points of S into In |S|/2 couples. The following two lemmas show how forming pairs of points facilitates the elimination of candidates for bridge points. LEMMA 3.1. Let p, q be a pair ofpoints of S. If x(p)=x(q) and y(p) > y(q) then q cannot be a bridge point. Proof. Trivial. LEMMA 3.2. Let p, q be a pair of points of S with x(p) < x(q), and let Spq be the slope of the straight line h through p and q. (1) If Spq > Sb then p cannot be a bridge point. (2) If Spq < Sb then q cannot be a bridge point. Proof (for case (1); the proof for case (2) is symmetrical). Assume p was a bridge point. By virtue of Spq > Sb and x(p) < x(q), q would lie above the bridge line b which would contradict the fact that b is a supporting line of S. Q.E.D. Proof. Trivial. To test whether Spq > Sb it suffices to find the supporting line h of S with slope Spq and to determine whether h contains points of S to the right or to the left of L. Of course, finding this supporting line h requires linear time which is clearly too expensive to be done for every one of the n/2 pairs individually. However, this problem can be overcome by judiciously choosing a slope Sh with the property that if Sh > Sb then Spq > Sh (and hence Spq > Sb) for a large number of pairs p, q and, if Sh < Sb then Spq < Sh (and hence Spq < Sb) for a large number of pairs p, q. A natural choice for an Sh with this property is the median of the slopes of the lines defined by the n/2 pairs of points.


This algorithm takes \( O(n \log{h}) \) steps in the \( \mathbb{R}^{2} \) case.
The algorithm needs a linear time median algorithm in two places, however you can take an element at random instead of the median and it becomes a randomized algorithm with the same expected complexity.

Graham Scan

This algorithm was created by Ronald Graham (1972).
The algorithm first chooses a point which is known to be part of the convex hull (eg. the leftmost point). Then the points are sorted by angle with this point. It then builds the convex hull in the following way: starting from the first point it continues to add points in order until there is a right turn. When a right turn is detected, it removes the last point that is part of the convex hull until there are only left turns.


This algorithm takes \( O(n \log{n}) \) steps in the \( \mathbb{R}^{2} \) case.
The number of steps is dominated by the sort operation, which takes \( O(n \log{n}) \) steps, while the remaining part of the algorithm takes \( \Theta(n) \) steps.