🟦 Convex Hull

In 2D game physics, the convex hull of a polygon is its minimal convex wrapper. Two convex polygons can be tested for intersection using the Separating Axis Theorem (SAT): if a line exists that separates the two hulls, they do not overlap — and only O(h₁ + h₂) candidate separating axes need to be tested (one per edge). The GJK (Gilbert-Johnson-Keerthi) algorithm extends this to 3D and handles curved objects by computing the Minkowski difference, achieving O(1) iterations in practice for simple shapes. Both SAT and GJK are fundamental tools in Unity, Bullet, and other physics engines.

Points that lie on a hull edge but are not vertices (they are collinear between two hull vertices) can be included or excluded depending on the algorithm variant. Standard Graham scan excludes collinear interior points (it removes them during the sort deduplication step), yielding the minimal vertex set. Some applications (e.g., polygon area computation) prefer including all boundary points. The choice affects h (hull size), runtime, and the behaviour of the cross-product orientation test (zero cross product must be handled carefully to avoid infinite loops in Jarvis march).

Chan's algorithm (Timothy Chan, 1996) achieves O(n log h) time, where h is the number of hull vertices — this is optimal because outputting h vertices takes Ω(h) time and sorting n points takes Ω(n log n). Chan's approach guesses h in doubling phases (try h = 2, 4, 8, …), runs a mini-Jarvis march that stops after h steps using a precomputed Graham scan on n/h groups of points as inner oracles. When the guess equals the true h, the algorithm terminates with a correct hull. Each phase costs O(n log h); the doubling adds only a constant factor, giving O(n log h) total.

In 2D linear programming, the feasible region defined by m inequality constraints is a convex polygon — a convex hull of the constraints' intersection points. The optimal solution of a linear programme always lies at a vertex of the feasible polytope. The simplex method traverses vertices of this polytope; interior-point methods traverse the interior. In higher dimensions (d variables, m constraints), computing the vertex enumeration of the feasible polytope is equivalent to computing a convex hull in d dimensions — a problem solved by double-description and beneath-beyond algorithms.

In 3D, the convex hull of n points is a convex polyhedron with at most O(n) vertices, edges, and faces (by Euler's formula: V − E + F = 2, and for convex polyhedra F ≤ 2n − 4). Algorithms include the 3D Graham scan (incremental insertion), divide-and-conquer (O(n log n)), and the gift-wrapping variant (Jarvis march in 3D). The QuickHull3D algorithm by Barber, Dobkin and Huhdanpaa (1996, qhull library) is the practical standard — used in SciPy's ConvexHull, MATLAB, and game engine physics tools.

Duplicate points (identical coordinates) must be handled explicitly; most implementations deduplicate the input before running the hull algorithm. In Graham scan, duplicate points would produce zero cross products causing ambiguity in the angular sort. In Jarvis march, selecting a duplicate as the next hull vertex could cause an infinite loop. A robust implementation either removes duplicates in O(n log n) preprocessing, or uses exact arithmetic with perturbation (symbolic perturbation / SOS — simulation of simplicity) to handle all degenerate configurations consistently.

There is a classical duality: the 2D Voronoi diagram of n points is equivalent to the projection of the 3D convex hull of the same points lifted to the paraboloid z = x² + y². Specifically, lift each point (xᵢ, yᵢ) to (xᵢ, yᵢ, xᵢ² + yᵢ²), compute the 3D convex hull, then project the lower hull faces back to 2D — the result is the Delaunay triangulation, and its dual graph is the Voronoi diagram. This means any O(n log n) 3D convex hull algorithm immediately gives an O(n log n) Voronoi algorithm, matching the classical Fortune's sweep-line algorithm.

In support vector machines (SVMs), the maximum-margin classifier between two classes of points corresponds to finding the closest points on the convex hulls of the two classes — the "minimum enclosing ball" dual. The SVM's support vectors are exactly the hull points closest to the separating hyperplane. Convex hulls also appear in data depth (Tukey depth, the "onion peeling" algorithm), anomaly detection (data points outside the hull are outliers), and in multi-objective optimisation where the Pareto frontier is a portion of the convex hull of feasible objective vectors.