Convex Hull Algorithms theory

The Convex Hull is the quintessential foundational problem of Computational Geometry, serving as the geometric equivalent of sorting in discrete algorithms.



1. Formal Mathematical Definitions:

Given a finite set of n points P = {p₁, p₂, ..., p_n} in Euclidean space ℝ²:

- Convex Combination: Any point x = ∑_{i=1}^n α_i p_i where α_i ≥ 0 and ∑ α_i = 1.

- Convex Set: A set S ⊂ ℝ² is convex if for all pairs of points a, b ∈ S, the line segment connecting them is completely contained in S: [a, b] ⊆ S.

- Convex Hull CH(P): The convex hull of P is defined equivalently as:

(a) The intersection of all convex sets containing P;

(b) The set of all convex combinations of points in P;

(c) The unique minimal-perimeter convex polygon enclosing all points in P.



2. Real-World Applications:

Convex hulls form the geometric core of modern spatial computing:

- Physics Engines & Video Games: Bounding volume hierarchies (BVH) utilize convex hulls for high-speed broad-phase collision detection (GJK algorithm);

- Computer Vision & Robotics: Minimum bounding boxes and convex deficiency trees represent segmented object silhouettes and obstacle boundaries for autonomous navigation;

- Geographic Information Systems (GIS): Computing territorial catchment basins, animal home ranges, and convex boundary enclosures;

- Statistics & Machine Learning: Support Vector Machines (SVM) identify maximum-margin hyperplanes that separate the convex hulls of distinct data classes.

In computational geometry, determining whether a sequence of three points makes a left turn, a right turn, or continues straight is the central primitive operation.



1. Determinant Derivation:

Consider three planar points p₁ = (x₁, y₁), p₂ = (x₂, y₂), and p₃ = (x₃, y₃). The directed vectors are v₁₂ = p₂ - p₁ = (x₂ - x₁, y₂ - y₁) and v₁₃ = p₃ - p₁ = (x₃ - x₁, y₃ - y₁). The signed area of the parallelogram spanned by v₁₂ and v₁₃ is given by the 2D cross product:

Δ(p₁, p₂, p₃) = v₁₂ × v₁₃ = det [ (x₂ - x₁) (x₃ - x₁) ; (y₂ - y₁) (y₃ - y₁) ]

Expanding the determinant yields the exact orientation formula:

Δ(p₁, p₂, p₃) = (x₂ - x₁)(y₃ - y₁) - (y₂ - y₁)(x₃ - x₁).



2. Orientation Classification:

- If Δ > 0: The vector v₁₃ lies to the left of v₁₂. The sequence (p₁, p₂, p₃) forms a strict Counter-Clockwise (CCW) Left Turn.

- If Δ < 0: The vector v₁₃ lies to the right of v₁₂. The sequence (p₁, p₂, p₃) forms a Clockwise (CW) Right Turn.

- If Δ = 0: The vectors v₁₂ and v₁₃ are collinear (the three points lie on a single straight line).



3. Elimination of Transcendental Arithmetic:

Naive geometry implementations often compute polar angles using transcendental functions: θ = atan2(y₂ - y₁, x₂ - x₁). Floating-point trigonometric functions consume 50 to 100 CPU cycles and suffer from roundoff error. The cross-product predicate uses only 2 multiplications and 4 subtractions (executing in ~2 CPU cycles on modern ALUs), completely eliminating trigonometric calls and providing exact integer arithmetic guarantees.

In 1972, Ronald Graham published 'An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set', inventing the first sub-quadratic convex hull algorithm.



1. Graham Scan Phases:

- Phase 1 (Pivot Selection): Find the point P_0 with the minimum y-coordinate (breaking ties by minimum x-coordinate). P_0 is guaranteed to be an extreme vertex on the convex hull.

- Phase 2 (Angular Sorting): Sort all remaining n - 1 points radially around P_0 in ascending polar angle order. This sorting takes O(n log n) time using comparison-based introsort.

- Phase 3 (The Perimeter Scan): Maintain a LIFO stack of candidate hull vertices, initialized with P_0, P_1, and P_2. For each subsequent point P_i (from 3 to n - 1):

While the stack has ≥ 2 vertices AND the orientation of (second-from-top, top, P_i) is NOT counter-clockwise (Δ ≤ 0):

Pop the top vertex from the stack (it is a reflex interior vertex);

Push P_i onto the stack.



2. Amortized Analysis of the Scanning Phase:

At first glance, the nested while-loop might appear to run in O(n²) time. However, aggregate amortized analysis reveals that:

- Each point P_i is pushed onto the stack exactly once across the outer loop (total n pushes);

- A point can only be popped from the stack if it was previously pushed;

- Once a point is popped, it is permanently discarded and can never be popped again!

Therefore, across all n iterations, the total number of stack pops cannot exceed n - 1. Because each iteration of the inner while-loop executes exactly one stack pop and one orientation evaluation, the total number of orientation tests during the perimeter scan is strictly bounded by:

T(n) = Pushes + Pops ≤ n + n = 2n tests.

Thus, after the O(n log n) sorting phase, the scanning phase executes in strictly O(n) linear time!

In 1973, R. A. Jarvis formulated the Gift Wrapping algorithm (Jarvis March), introducing the powerful concept of Output-Sensitive Complexity to computational geometry.



1. Algorithm Mechanics:

Jarvis March simulates wrapping a taut string around the point set:

- Start at the guaranteed hull vertex P_0 (minimum y-coordinate);

- To find the next hull vertex, cast a ray and rotate it counter-clockwise until it strikes the next point. In terms of orientation tests: iterate through all n points in P, maintaining the point with the most counter-clockwise orientation relative to the current hull vertex;

- Append the winning point to the hull and repeat the search from this new vertex;

- Terminate when the search returns to the starting vertex P_0.



2. Output Sensitivity & Asymptotics:

Let h denote the number of vertices on the final convex hull (where 3 ≤ h ≤ n):

- Each hull vertex requires inspecting all n points via cross-product tests;

- To discover all h hull vertices, Jarvis March executes exactly h rounds, performing O(n · h) total operations.



3. Comparative Crossover Analysis:

- When h << log n (e.g., in a circle with points concentrated inside, where h = 4 or 5 vertices), Jarvis March runs in O(n) time, running significantly faster than Graham Scan's O(n log n) sorting bottleneck;

- However, when h ≈ n (e.g., points situated along an ellipse or circular perimeter where all points belong to the hull), Jarvis March degrades catastrophically to O(n²), making Graham Scan dramatically superior.

Quickhull—formulated independently by W. Eddy (1977) and A. Bykat (1978)—is a divide-and-conquer algorithm directly analogous to C. A. R. Hoare's Quicksort.



1. Divide-and-Conquer Mechanics:

- Step 1 (Extreme Baseline): Find the points with minimum and maximum x-coordinates: P_min and P_max. The directed line segment L = [P_min, P_max] divides the remaining points into two subsets: S_upper (points to the left of L, Δ > 0) and S_lower (points to the right of L, Δ < 0);

- Step 2 (Apex Discovery): For S_upper, find the point P_apex that is furthest from line L (maximizing triangle area Δ(P_min, P_max, P_apex));

- Step 3 (Interior Elimination): Points falling inside the triangle formed by (P_min, P_max, P_apex) cannot possibly belong to the convex hull and are immediately discarded;

- Step 4 (Recursive Bisection): The segments [P_min, P_apex] and [P_apex, P_max] define two new outward-facing half-planes. Recursively apply Quickhull to the points lying outside these segments.



2. Complexity & Pathological Degradation:

- Average-Case Complexity: On uniformly distributed point sets, each apex discards a large fraction of interior points, leading to a recurrence T(n) = 2T(n/2) + O(n), which solves by the Master Theorem to O(n log n) expected time;

- Worst-Case Quadratic Degradation: If points are arranged along a concave circular curve such that each step partitions the remaining points into 1 and n - 1 (analogous to sorted inputs in Quicksort), Quickhull degrades to O(n²) time.

In 1996, Timothy M. Chan achieved a monumental breakthrough in theoretical computer science by publishing 'Optimal Output-Sensitive Convex Hull Algorithms in Two and Three Dimensions', unifying Graham Scan and Jarvis March into an optimal O(n log h) algorithm.



1. The Information-Theoretic Lower Bound:

Michael Shamos (1978) proved that sorting n real numbers can be reduced to computing the convex hull of n points (mapping numbers x_i ⟶ (x_i, x_i²)). Consequently, any comparison-based convex hull algorithm requires at least Ω(n log n) worst-case time. When parameterized by the output hull size h, the true information-theoretic lower bound is Ω(n log h).



2. Chan's Two-Level Hybrid Architecture:

Chan combined the strengths of Graham Scan and Jarvis March:

- Partitioning: Divide the n points into r = ⌈n/m⌉ groups of size m (where m is an initial guess for h);

- Mini-Hulls: For each group, compute its convex hull in O(m log m) time using Graham's scan. The total time for all r groups is r · O(m log m) = (n/m) · O(m log m) = O(n log m);

- Wrapped Merging: Run Jarvis March on the r mini-hulls! At each step of Jarvis March, instead of inspecting all n points individually, use binary search on each mini-hull to find its tangent point in O(log m) time. Evaluating tangents across all r mini-hulls takes r · O(log m) = (n/m) log m time per hull vertex;

- For m steps, the wrapping takes m · (n/m log m) = O(n log m) time!



3. Doubling Search Guess for m:

Because h is unknown a priori, Chan squares the guess m at each iteration: m = 2^{2^t} for t = 1, 2, 3... The algorithm terminates as soon as m ≥ h, and the geometric series ∑ O(n log(2^{2^t})) converges strictly to O(n log h)!

Geometric algorithms implemented using standard IEEE 754 double-precision floating-point arithmetic are notorious for fatal robustness failures in production systems.



1. Floating-Point Roundoff & Topological Inconsistency:

The 2D orientation determinant Δ = (x₂ - x₁)(y₃ - y₁) - (y₂ - y₁)(x₃ - x₁) involves products of differences. When three points are nearly collinear, roundoff errors in the least significant bits can cause the calculated value of Δ to have the wrong sign:

- An actual left turn can be evaluated as a right turn;

- This causes Graham Scan or Quickhull to produce self-intersecting polygons, invert winding orders, discard true hull vertices, or enter infinite loops!



2. Jonathan Shewchuk's Adaptive Precision Arithmetic:

In 1997, Jonathan Shewchuk solved this industry-wide crisis by designing 'Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates':

- Fast Hardware Filter: First, compute Δ using standard IEEE 754 64-bit hardware floating-point operations. Calculate an error bound ε based on the maximum coordinates of the inputs;

- Bound Testing: If |Δ| > ε, the floating-point result is guaranteed to have the correct sign, executing in just a few clock cycles;

- Adaptive Expansion: If |Δ| ≤ ε, the computation is in the precision danger zone! The algorithm switches dynamically to multiple-precision arithmetic using expansions (arrays of non-overlapping floating-point words) to compute the exact determinant sign with zero rounding error.

Modern spatial libraries (CGAL, GEOS, JTS) mandate adaptive precision predicates to guarantee complete mathematical robustness.