## Convex Hull

We start with the definition of a convex set: in convex geometry, a convex set is a subset of an affine space that is closed under convex combinations. More specifically, in Euclidean spaces, a convex region is a region where, for every pair of points within the region, every point on the straight line segment that joins the pair of points is also within the region.

#### Definition 1

$$\text{A set} \space P \subset \mathbb{R^d} \space \text{is} \space \mathbf{convex} \space \text{if} \space \overline{pq} \subseteq P, \space \text{for any} \space p, q \in P.$$

The polygon depicted in (a) is convex, and so are a straight line, a triangle, a rectangle, and more generally, any convex polygon, a circle, and the entire plane. On the other hand, the polygon shown in (b) is not convex because there are some pairs of points for which the connecting line segment is not completely contained within the polygon. An immediate consequence of the definition follows:

#### Observation 2

$$\text{For any family} \space \left ( P_{i} \right )_{i \in I} \space \text{of convex sets, the intersection} \space \cap _{i \in I} P_{i} \space \text{is convex.}$$

## Convexity

Consider $P \subseteq \mathbb{R^d}$, The linear hull

$$lin(P) := \left \{ q \mid q = \sum \lambda_{i}p_{i} \wedge \forall i: p_{i}\in P, \lambda_{i} \in \mathbb{R} \right \}$$

is the set of all linear combinations of $P$ (smallest linear subspace containing $P$). For instance, if $P = \left \{ p \right \} \subset \mathbb{R}^{2} \setminus \left \{ 0 \right \}$ then $lin(P)$ is the line through $p$ and the origin. Similarly, the affine hull

$$aff(P) := \left \{ q \mid q = \sum \lambda_{i}p_{i} \wedge \sum \lambda_{i} = 1 \wedge \forall i: p_{i}\in P, \lambda_{i} \in \mathbb{R} \right \}$$

is the set of all affine combinations of $P$ (smallest affine subspace containing $P$). For instance, if $P = \left \{ p, q \right \} \subset \mathbb{R}^{2}$ and $p \neq q$  then $aff(P)$ is the line through $p$ and $q$.

By restricting the coefficients used in linear combinations, we can define the related concepts of affine combination, conical combination, and convex combination, and the associated notions of sets closed under these operations:

Convexity can also be described in a very similar way algebraically:

#### Proposition 3

For any $P \subseteq \mathbb{R}^{d}$ we have

$$conv(P) = \left \{ \sum_{i = 1}^{n} \lambda_{i}p_{i} \mid n \in \mathbb{N} \wedge \sum_{i = 1}^{n} \lambda_{i} = 1 \wedge \forall i \in \{1,...n\} : \lambda_{i} \geq 0 \wedge p_{i} \in P \right \}.$$

With Proposition 3 and Observation 2, we can define convex hull as:

#### Definition 4

$$\text{The} \space \mathbf{convex} \space \mathbf{hull} \space conv(P) \space \text{of a set} \space P \subseteq \mathbb{R^d} \space \text{is the intersection of all convex supersets of} \space P.$$

In a similar way we want to describe convex sets using as few entities as possible, which leads to the notion of extreme point, as defined below.

#### Definition 5

The convex hull of a finite point set $P \subset \mathbb{R}^{d}$ forms a convex polytope. Each $p \in P$ for which $p \notin conv(P \setminus \left \{ p \right \})$ is called a vertex of conv(P). A vertex of conv(P) is also called an extreme point of P. A convex polytope in $\mathbb{R}^{2}$ is called a convex polygon.

Essentially, the following proposition shows that the term vertex above is well defined.

#### Proposition 6

$$\text{A convex polytope in } \mathbb{R}^{d} \text{ is the convex hull of its vertices.}$$

Intuitively, the convex hull of a set of n points in the plane is the smallest convex polygon that contains all of them either inside or on its boundary. A formal definition of the convex hull that is applicable to arbitrary sets, including sets of points that happen to lie on the same line, follows:

#### Definition 7

The convex hull of a set $S$ of points is the smallest convex set containing $S$.

## Algorithms

The following algorithms construct the convex hull of a finite point set $P \subseteq \mathbb{R}^{2}$. Time complexity of each algorithm is stated in terms of the number of inputs points $n$ and the number of points on the hull $h$. Note that in the worst case $h$ may be as large as $n$.

#### Jarvis march – O(nh)

Find a point $p_{0}$ that is a vertex of conv(P) (e.g., the one with smallest x-coordinate). “Wrap” P starting from $p_{0}$, i.e., always find the next vertex of conv(P) as the one that is leftmost with respect to the direction given by the previous two vertices.

Besides the lexicographic comparison mentioned above, Jarvis March needs one more geometric predicate: the rightturn (or orientation test). Here we can prove that: for three points $\left ( p_{x}, p_{y} \right ), \left ( q_{x}, q_{y} \right ), \left ( r_{x}, r_{y} \right ) \in \mathbb{R}^{2}$, the sign of the determinant

$$\begin{vmatrix} p_{x} & p_{y} & 1 \\ q_{x} & q_{y} & 1 \\ r_{x} & r_{y} & 1 \end{vmatrix}$$

determines if $r$ lies to the right, to the left or on the directed line $\vec{pq}$ (point $r$ is to the left of the line $\vec{pq}$ directed from point $p$ to point $q$ if $pqr$ forms a counterclockwise cycle). The sign of this expression is positive if and only if the point $\left ( r_{x}, r_{y} \right )$ is to the left of the line $\vec{pq}$. Using this formula, we can check in constant time whether a point lies to the left of the line determined by two other points as well as find the distance from the point to the line.

For every output point the above algorithm spends $n$ rightturn tests, which is $\Rightarrow O\left ( nh \right )$ in total. In the worst case we have $h = n$, that is, $O\left ( n^{2} \right )$ rightturn tests.

The algorithm may have to cope with various degeneracies:

• Several points have smallest x-coordinate $\Rightarrow$ lexicographic order:
$$\left ( p_{x}, p_{y} \right ) < \left ( q_{x}, q_{y} \right ) \Leftrightarrow p_{x} < q_{x} \vee p_{x} = q_{x} \wedge p_{y} < q_{y}.$$
• Three or more points collinear $\Rightarrow$ choose the point that is farthest among those that are leftmost.

Jarvis March has a remarkable property that is called output sensitivity: the runtime depends not only on the size of the input but also on the size of the output. For a huge point set it constructs the convex hull in optimal linear time, if the convex hull consists of a constant number of vertices only, but the worst case performance of Jarvis March is suboptimal.

A C++ implementation of Jarvis March can be found here.

#### Graham Scan — O(nlogn)

This algorithm for computing the convex hull of a set $P$ of $n$ points in the plane consists of the following three parts:

• Select a base point $p_{0} \in P$, normally this is the point with minimum y-coordinate. In case of the tie, we select leftmost point (minimum x-coordinate) in the set.
• Sort the remaining points of $P$ (that is, $P \setminus \left \{ p_{0} \right \}$) in lexicographical order by polar angle, measured in radian. Interior points on the ray cannot be a convex hull points and remove these points during sort. Once the points are sorted, we connected them in counterclockwise order with respect to the anchor point $p_{0}$. The result is a simple polygon.
• After pushing the anchor point $p_{0}$ onto the stack $S$, we scan through the points in counterclockwise order, maintaining at each step a stack $S$ containing a convex chain surrounding the points scanned so far. Each time we consider the new point $p_{i}$, we perform the following tereest:
• If $p_{i}$ forms a left turn with the last two points in the stack $S$, or if $S$ contains fewer than two points, then push $p_{i}$ onto the stack $S$.
• Otherwise, pop the last point from the stack $S$ and repeat the test for $p_{i}$.

When we return to the base point $p_{0}$, at which point stack $S$ stores the vertices of the convex hull of $P$ in counterclockwise order.

A C++ implementation of Graham Scan can be found here.

An animation of Graham Scan can be found here.

#### Monotone Chain — O(nlogn)

This algorithm first sorts the points lexicographically (first by x-coordinate, and in case of a tie, by y-coordinate), and then constructs the upper and the lower hulls of the points in $O\left ( n \right )$ time.

An upper hull is the part of the convex hull, which is visible from the above. It runs from its rightmost point to the leftmost point in counterclockwise order. Lower hull is the remaining part of the convex hull.

A C++ implementation of Andrew’s Monotone Chain can be found here.

#### Quick Hull — O(nlogn)

Let $S$ be a set of $n > 1$ points $p_{1}\left ( x_{1}, y_{1} \right ),...p_{n}\left ( x_{n}, y_{n} \right )$ in the Cartesian plane. We assume that the points are sorted in nondecreasing order of their x coordinates, with ties resolved by increasing order of the y coordinates of the points involved. The leftmost point $p_{1}$ and the rightmost point $p_{n}$ are two distinct extreme points of the set’s convex hull.

Let $\vec{p_{1}p_{n}}$ be the straight line through points $p_{1}$ and $p_{n}$ directed from $p_{1}$ to $p_{n}$. This line separates the points of $S$ into two parts: the left part $S_{1}$ and the right part $S_{2}$, while the points of $S$ on the line $\vec{p_{1}p_{n}}$ other than $p_{1}$ and $p_{n}$ cannot be extreme points of the convex hull.

If $S_{1}$ is empty, the upper hull is simply the line segment with the endpoints at $p_{1}$ and $p_{n}$. For points in $S_{1}$ which is not empty, we can find a point $p_{max}$ which is the furthest from line $\vec{p_{1}p_{n}}$, and if there is a tie, select the point that maximizes the angle $\angle p_{max}p_{1}p_{n}$. Then the algorithm identifies all the points of set $S_{1}$ that are to the left of the line $\vec{p_{1}p_{max}}$ as $S_{1,1}$, and the points of $S_{1}$ to the left of the line $\vec{p_{max}p_{n}}$ will make up the set $S_{1,2}$. We can prove that:

• $p_{max}$ is a vertex of the upper hull.
• The points inside $\bigtriangleup p_{1}p_{max}p_{n}$ cannot be vertices of the upper hull (and hence can be eliminated).
• There are no points to the left of both lines $\vec{p_{1}p_{max}}$ and $\vec{p_{max}p_{n}}$.

Therefore, the algorithm can continue constructing the upper hulls of $p_{1} \cup S_{1,1} \cup p_{max}$ and $p_{max} \cup S_{1,2} \cup p_{n}$ recursively and then simply concatenate them to get the upper hull of the entire set $p_{1} \cup S_{1} \cup p_{n}$.

A C++ implementation of Quick Hull can be found here.

An animation of Quick Hull can be found here.

#### Divide and Conquer — O(nlogn)

Like Monotone Chain, we need to sort the points lexicographically, then the original set $S$ can be divided into two sets $L$ and $R$: $L$ containing the leftmost $\left \lceil n/2 \right \rceil$ points and $R$ containing the rightmost $\left \lfloor n/2 \right \rfloor$ points. Compute the convex hulls of the subsets $L$ and $R$ recursively, say $CH(L)$ and $CH(R)$. For the convex hull of a set contains 3 or less points is the set itself, we can return them immediately.

Merge $CH(L)$ and $CH(R)$ by computing the upper and lower tangents of $CH(L)$ and $CH(R)$ and discarding all the points lying between these two tangents. Let’s concentrate on the lower tangent — since the upper tangent is symmetric — which meets the following requirement:

$$\left \{ \begin{vmatrix} p_{x} & p_{y} & 1 \\ q_{x} & q_{y} & 1 \\ r_{x} & r_{y} & 1 \end{vmatrix} \geq 0 \mid p \in CH(L) \wedge q \in CH(R) \wedge \forall r \in CH(L) \cup CH(R) \setminus \left \{ p, q \right \} \right \}$$

Let $p$ to be the rightmost point of $CH(L)$ and $q$ to be the leftmost point of $CH(R)$, we now move point $p$ and $q$ as follows:

1. As long as there is a point in $CH(L)$ lies to the right of $\vec{pq}$, move $p$ to the next clockwise point of $CH(L)$;
2. As long as there is a point in $CH(R)$ lies to the right of $\vec{pq}$, move $q$ to the next counterclockwise point of $CH(R)$;
3. Repeat (1) and (2) until there isn’t any point in $CH(L)$ or $CH(R)$ lies to the right of $\vec{pq}$, $\vec{pq}$ is the lower tangent.

A C++ implementation of Divide and Conquer can be found here.

#### Incremental Algorithm — O(nlogn)

Choose three random points which are not colinear as the initial convex hull $S$. Find the leftmost point $L$ in $S$ and the rightmost point $R$ in $S$, $\vec{LR}$ separates $S$ into two hulls: the upper hull and the lower hull.

Here we use two balanced binary search trees(say $T_{u}$ and $T_{l}$) to represent the upper hull and the lower hull. The internal nodes store the x-coordinate of the point and the point itself, as follows:

The incremental algorithm consists of two operations: locate(q) and insert(q):

1. locate(q) determines if $q$ lies inside, outside or on $S$. To perform locate(q), we search for point $q$ in $T_{u}$ and $T_{l}$ to find edge or vertex on the upper/lower hull whose horizontal span includes $q$. Here are four cases:
1. No such edges or vertices exist: $q$ lies outside of $S$ and it’s the leftmost/rightmost point by far, so invoke insert(q) to update both the lower hull and the upper hull;
2. $q$ lies above/on the edge of $T_{l}$ and below/on the edge of $T_{u}$: pass;
3. $q$ lies above the edge of $T_{u}$ and $T_{l}$: invoke insert(q) to update the upper hull;
4. $q$ lies below the edge of $T_{u}$ and $T_{l}$: invoke insert(q) to update the lower hull;
2. insert(q) merges point $q$ into the upper/lower hull. e.g. here is the algorithm for case (c): find the edge whose horizontal span includes $q$, let $l$ and $r$ to be the left endpoint and right endpoint of the edge:
1. Move $l$ counterclockwise until all the other points of $S$ lie to the right of $\vec{lq}$;
2. Move $r$ clockwise until all the other points of $S$ lie to the left of $\vec{rq}$;
3. Replace all the points between $l$ and $r$(exclusive) with $q$.

The upper hull and the lower hull can then be concatenated to form the complete convex hull.

#### Chan’s Algorithm — O(nlogh)

In the planar case, this algorithm combines an $O\left ( n \cdot \log n \right )$ algorithm (Graham scan, for example) with Jarvis march ($O\left ( n \cdot h \right )$), in order to obtain an optimal $O\left ( n \cdot \log h \right )$ time.

1. Preprocess the points: Divide the $n$ points into $\left \lceil n/m \right \rceil$ groups of size $m$. Compute the convex hull of each groups by any $O(n \log n)$ algorithm we discussed before. The convex polygon of each group has at most $m$ vertices. So each group costs $O(m \cdot \log m)$ time. $\left \lceil n/m \right \rceil$ groups cost $O(n / m \cdot (m \cdot \log m)) = O(n \cdot \log m)$ time. Then store $\left \lceil n/m \right \rceil$ polygons in $\left \lceil n/m \right \rceil$ binary tree for Wrapping Step.
2. Wrapping Step: Scan all $\left \lceil n/m \right \rceil$ polygons and compute tangents or supporting lines of the polygons through the current vertex $p_{k}$. The tangent finding takes $O(\log m)$ time for a convex polygon so $O(n / m \cdot \log m)$ time for $\left \lceil n/m \right \rceil$ polygons. Since the convex hull has $h$ vertices, $h$ wrapping steps cost $O(h \cdot n / m \cdot \log m)$.

The two steps cost $O(n \cdot \log m + h \cdot n / m \cdot \log m)$, by choosing $m = h$, the time complexity is $O(n \cdot \log h)$. However, choosing different form of $m$ lead to different time complexity($t$ isVariable of iteration, relative to $m$):

Chan’s paper contains several suggestions that may improve the practical performance of the algorithm, for example:

• When computing the convex hulls of the subsets, eliminate the points that are not in the convex hull from consideration in subsequent executions.
• The convex hulls of larger point sets can be obtained by merging previously calculated convex hulls, instead of recomputing from scratch.
• With above idea, the dominant cost of algorithm lies in the pre-processing, i.e., the computation of the convex hulls of the groups. To reduce this cost, we may consider reusing hulls computed from the previous iteration and merging them as the group size is increased.

#### Kirkpatrick–Seidel Algorithm — O(nlogh)

We can also achieve $O \left ( n \cdot \log h \right )$ running time using a variant of the earlier divide-and-conquer algorithm Quick Hull. This algorithm avoids the $O \left ( n^2 \right )$ worst-case running time by choosing an approximately balanced partition of the points; at the same time, the algorithm prunes away a large subset of the interior points whenever possible.

Consider the minimum and maximum x-coordinates of points in $P$, denoted $x_{min}$ and $x_{max}$. Convex Hull of $P$ can be be viewed as a pair of convex chains called the upper hull and the lower hull of $P$. The following algorithm will only compute the upper-hull of P, since the lower hull is symmetric.

1. Compute the median $x_{med}$ of x-coordinates of points in $P$, this can be done in $O(n)$ time by the algorithm called median of medians.
2. Partition $P$ into two sets $L$ and $R$ each of size about $n / 2$ around the median $x_{med}$.
3. Find the upper bridge $\overline{pq}$ of $L$ and $R$, $p \in L$, and $q \in R$. This will take $O(n)$ time and we’ll discuss it later.
4. $L^{'} \leftarrow \left \{ r \in L \mid x(r) \leq x(p) \right \}$
5. $R^{'} \leftarrow \left \{ r \in R \mid x(r) \geq x(q) \right \}$
6. $LUH \leftarrow UpperHull(L^{'})$
7. $RUH \leftarrow UpperHull(R^{'})$
8. return the concatenated list $LUH$, $\overline{pq}$, $RUH$ as the upper hull of $P$.

#### Finding the Upper Bridge in Linear Time

We assume that the bottom line of the upper hull $\overleftrightarrow{az}$ is horizontal, and that $a$ lies to the left of $z$. This assumption can be enforced by a change of coordinates, but in fact, if everything is implemented using the correct algebraic primitives, no such transformation is necessary.

We start by arbitrarily pairing up the points in $P$. Let $q,r$ be the pair whose connecting line has median slope among all $n/2$ pairs; we can find this pair in $O \left ( n \right )$ time. We now choose the pivot point $p$ to be the point in $P$ furthest above the line $\overleftrightarrow{qr}$, rather than the point furthest above the baseline $\overleftrightarrow{az}$.

Next we prune the set $P$ as follows: For each pair $s,t$ of points in $P$ , we discard any point in the subset $\left \{ a,z,p,s,t \right \}$ that is inside the convex hull of those five points. This pruning step automatically discards any points inside the triangle $\bigtriangleup apz$, just like the earlier algorithm, but other points may be removed as well.

Back to step (6), we can conclude that the subset $LUH$ contains at most $3n/4$ points . Consider a pair $s,t$ from our arbitrary pairing of $P$. If both of these points are in $LUH$ , they must satisfy two conditions:

1. they both lie to the left of $\overrightarrow{ap}$.
2. the slope of $st$ is larger than the slope of $qr$.

By definition, less than half the pairs have slope larger than the median slope. Thus, in at least $n/4$ pairs, at least one point is not in $LUH$. Symmetrically, the subset $RUH$ also contains at most $3n/4$ points.

Let $T(n, h)$ denote the worst-case time complexity of the algorithm. Suppose $LUH$ and $RUH$ in steps (6) and (7) consist of $h_{1}$ and $h_{2}$ edges, respectively. Since $\lvert L^{'} \rvert \leq \lvert L \rvert$ and $\lvert R^{'} \rvert \leq \lvert R \rvert$, the two recursive calls in steps 6 and 7 take time $T(n_{1}, h_{1})$ and $T(n_{2}, h - h_{1})$ time. Therefore $T(n, h) = O(n) + T(n_{1}, h_{1}) + T(n_{2}, h - h_{1})$, where $n_{1} + n_{2} \leq n$ and $max \left \{ n_{1}, n_{2} \right \} \leq 3n/4$.

Let’s assume that the $O(n)$ term is at most $\alpha n$ for some constant $\alpha$. The following inductive proof implies that $T(n,h) \leq \beta \cdot n \cdot lnh$ for some constant $\beta$:

\begin{aligned} T(n,h) &\leq \alpha \cdot n + T(n_{1},h_{1}) + T(n_{2},h - h_{1}) \\ &\leq \alpha \cdot n + \beta \cdot n_{1} \cdot \ln h_{1} + \beta \cdot n_{2} \cdot \ln \left ( h - h_{1} \right ) \\ &\leq \alpha \cdot n + \beta \cdot n_{1} \cdot \ln h_{1} + \beta \cdot \left (n - n_{1} \right ) \cdot \ln \left ( h - h_{1} \right ) \\ &\leq \alpha \cdot n + \beta \cdot \frac{3n}{4} \cdot \ln h_{1} + \beta \cdot \frac{n}{4} \cdot \ln \left ( h - h_{1} \right ) \\ &\leq \alpha \cdot n + \beta \cdot \frac{n}{4} \left ( 3 \ln h_{1} + \ln \left ( h - h_{1} \right ) \right )\\ &\leq \alpha \cdot n + \beta \cdot \frac{n}{4} \left (\underset{x}{max} \left ( 3 \ln x + \ln \left ( h - x \right ) \right ) \right )\\ \end{aligned}

The function $3 \ln x + \ln (h - x)$ is maximized when its derivative is zero:

$\frac{\mathrm{d}}{\mathrm{d} x}\left ( 3 \ln x + \ln \left ( h - x \right ) \right ) = \frac{3}{x} - \frac{1}{h - x} = 0 \Rightarrow x = \frac{3h}{4}$

Thus,

\begin{aligned} T(n,h) &\leq \alpha \cdot n + \beta \cdot \frac{n}{4} \left ( 3 \ln \frac{3h}{4} + \ln \frac{h}{4} \right )\\ &\leq \alpha \cdot n + \beta \cdot n \cdot \ln h + \beta \cdot n \left ( \frac{3}{4} \ln \frac{3}{4} + \frac{1}{4} \ln \frac{1}{4} \right )\\ &\leq \beta \cdot n \cdot \ln h + \left ( \alpha - 0.562336 \beta \right ) \cdot n \end{aligned}

If we assume $\beta \geq 2 \alpha$, the time complexity of $T(n, h)$ is $O(n \cdot \log h)$.

#### Melkman’s Algorithm on Simple Polygon — O(n)

Let the simple polygon chain be $\mathbf{C} = \left ( v_{0}, v_{1},...,v_{n-1} \right )$, with vertices $v_{i}$ and edges $v_{i}v_{i+1}$, etc. The algorithm uses a dequeue $\mathbf{D} = \left \langle d_{b}, d_{b+1},...,d_{t} \right \rangle$ to represent the convex hull.

It will always be the case that $d_{b}$ and $d_{t}$ (the bottom and top elements of the deque) refer to the same vertex of $\mathbf{C}$, and this vertex will always be the last one that we added to the convex hull.

We step along the simple polygon chain, examining vertices $v_{i}$ in the order they appear along the simple polygon chain. The deque $\mathbf{D}$ stores the current convex hull. We step along the simple polygon chain until we find the first vertex $v_{i}$ that lies outside of the convex hull specified by $\mathbf{D}$: the property of the polygon being simple guarantees that this test (to see if $v_{i}$ lies inside the current hull or not) can be done in contant time by checking to see if $v_{i}$ lies in the exterior cone determined by the point $d_{b}=d_{t}$. The fact that the polygon is simple implies that the only way for the polygon to emerge from the convex hull $\mathbf{D}$ is for the polygon to exit the hull through one of the two edge ($d_{b}d_{b+1}$ or $d_{t-1}d_{t}$) adjacent to the point $d_{b}=d_{t}$ that last was added to $\mathbf{D}$(Exiting through another edge would imply that the polygon crossed itself). By localizing where the chain can erupt from the hull, we have a constant-time method to test if $v_{i}$ is in the hull, and, if it is not, we can do repairs to $\mathbf{D}$ by starting at a known point, $d_{b}=d_{t}$ and popping / removing entries until we restore convexity.

At last, here is an online example of Melkman’s algorithm with a more intuitive explanation.