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.

upper hull and lower hull
upper hull and lower hull
  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.

Both points discarded
Both points discarded
One point survives
One point survives
Both points survive
Both points survive

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.

Leave a Reply

Your email address will not be published. Required fields are marked *

*