25 Convex Hulls - Geometry, Algorithms, and Complexity

Lecture from: 22.05.2025 | Video: Homelab

In this lecture, we focus on computing the convex hull of a finite set of points in the plane. We explore definitions, geometric properties, key algorithms (including Jarvis’ March and Local Repair), and complexity bounds.

What is a Convex Set?

A subset $C\subseteq {\mathbb{R}}^d$ is called convex if, for any two points $v_0,v_1\in C$, the entire line segment between them is also contained in $C$. Formally:

This means the set “contains all its straight lines” - there are no “indentations.”

What is a Convex Hull?

Given a set of points $P\subseteq {\mathbb{R}}^d$, the convex hull of $P$, denoted $\text{conv}(P)$, is the smallest convex set containing all points in $P$. Formally:

That is, the convex hull is the intersection of all convex sets containing $P$. For a finite set $P\subset {\mathbb{R}}^2$, the convex hull always exists and is unique.

Representation of the Convex Hull

In ${\mathbb{R}}^2$, the convex hull of a finite set $P$ is a convex polygon whose vertices are a subset of $P$. This polygon is described by the sequence:

traversed counterclockwise. The order is essential - it defines the edges of the polygon.

We assume general position: no three points are collinear and no two points share an x-coordinate.

Determining Convex Hull Edges

A directed edge $(q,r)$ is a boundary edge (Randkante) if all other points in $P\setminus \{q,r\}$ lie to the left of the directed line from $q$ to $r$.

Formally, for three points $p,q,r\in {\mathbb{R}}^2$, define:

Then:

• $\text{det}(p,q,r)>0$ ⇔ $p$ lies left of $\overrightarrow{qr}$
• $\text{det}=0$ ⇔ points are collinear
• The area of triangle $△pqr$ is $\frac{1}{2}|\text{det}(p,q,r)|$

Algorithms

Naive Algorithm: $O(n^3)$

We could test every pair $(q,r)\in P^2$ and check if all other points lie on one side (using $O(n)$ tests). There are $O(n^2)$ pairs, each tested in $O(n)$ ⇒ total time $O(n^3)$.

Jarvis March (a.k.a. Gift Wrapping)

An output-sensitive algorithm - runtime depends on the number of convex hull vertices $h$.

JarvisWrap

Runtime

• Each of the $h$ convex hull vertices is found in $O(n)$ ⇒ $O(nh)$ total.
• Best case: $h=O(1)$ ⇒ $O(n)$
• Worst case: $h=\Theta (n)$ ⇒ $O(n^2)$

Local Repair: Towards an Optimal Algorithm

Idea: Start with a polygonal chain that contains all points and is easy to fix. Use local convexity checks to iteratively remove non-convex corners.

Step 1: Start Polygon

Sort the points by increasing x-coordinate $(p_1,\dots ,p_n)$. Form the polygon:

This polygon contains all points.

Step 2: Local Convexity Check

For any triple $(q_{i-1},q_i,q_{i+1})$, remove $q_i$ if it lies to the left of the line from $q_{i-1}$ to $q_{i+1}$. This is a non-convex corner.

Repeat until all corners are convex ⇒ the resulting polygon is the convex hull.

Efficient Implementation: LocalRepair

This version achieves $O(n\log n)$ time total.

LocalRepair

Assume input is sorted by x-coordinate. Use two passes:

1. Lower Hull (left to right)
2. Upper Hull (right to left)

Maintain a stack of vertices and check for convexity at each step.

Correctness and Runtime

• Each vertex is pushed and popped at most once ⇒ $O(n)$ operations.
• Sorting takes $O(n\log n)$, so total time is $O(n\log n)$.
• This is optimal for comparison-based models.

Lower Bound via Reduction from Sorting

To show a lower bound, consider the following reduction:

Let $x_1,...,x_n\in \mathbb{R}$ and define $p_i=(x_i,x_i^2)$. These lie on the parabola $y=x^2$.

Then the convex hull is simply the lower and upper envelope of the parabola.

Sorting $x_i$‘s can be recovered from the convex hull ⇒ any convex hull algorithm must take $\Omega (n\log n)$ in the worst case.

Handling Degeneracies and Precision

Real implementations must deal with:

• Duplicate points
• Collinear points
• Floating point rounding errors (especially in orientation tests)

Solutions include:

• Lexicographic sorting to choose canonical starting points.
• Comparing orientation using robust predicates or exact arithmetic libraries.

Summary