# Convex hull
The convex hull of a set of points is the smallest convex set that contains them: the set of all convex combinations of the points, or geometrically, the shape a rubber band would form when stretched around them[1](https://doc.cgal.org/Manual/3.1/doc_html/cgal_manual/Convex_hull_d/Chapter_main.html) • [2](https://postgis.net/docs/manual-3.7/en/ST_ConvexHull.html). For a finite point set in the plane the hull is a convex polygon whose vertices are points of the set; in higher dimensions it is a convex polytope[1](https://doc.cgal.org/Manual/3.1/doc_html/cgal_manual/Convex_hull_d/Chapter_main.html). Computing it is one of the founding problems of computational geometry, and hull algorithms and hull data structures now serve fields from GIS and collision detection to linear programming[3](https://cise.ufl.edu/~ungor/courses/fall06/papers/QuickHull.pdf).
| Key fact | Detail |
|---|---|
| Definition | The smallest convex set containing a set S; equivalently all convex combinations of points of S[1](https://doc.cgal.org/Manual/3.1/doc_html/cgal_manual/Convex_hull_d/Chapter_main.html) • [4](https://elliotpaquette.github.io/high-dimensional-probability/lectures/02-convex-hulls.html) |
| Carathéodory's theorem | In \( \mathbb{R}^d \), every point of the hull is a convex combination of at most \( d+1 \) points of the set[4](https://elliotpaquette.github.io/high-dimensional-probability/lectures/02-convex-hulls.html) |
| Planar complexity | Graham's scan (1972) runs in \( O(n \log n) \); output-sensitive algorithms achieve \( O(n \log h) \), where h is the number of hull vertices[5](https://dblp.org/rec/journals/ipl/Graham72.html) • [6](https://arxiv.org/abs/1810.00455) |
| Quickhull | Barber, Dobkin, and Huhdanpaa's 1996 algorithm combines 2-d Quickhull with the general-dimension Beneath-Beyond method; Qhull is its implementation[3](https://cise.ufl.edu/~ungor/courses/fall06/papers/QuickHull.pdf) |
| Floating-point handling | Qhull's defaults merge facets ('C-0' in 2-d to 4-d, 'Qx' in 5-d and higher); option 'QJ' joggles the input instead[7](https://www.qhull.org/html/qh-impre.htm) |
| Related constructions | Delaunay triangulation, Voronoi diagrams, and halfspace intersection all reduce to convex hulls[3](https://cise.ufl.edu/~ungor/courses/fall06/papers/QuickHull.pdf) |
| Software | Qhull backs SciPy's ConvexHull; CGAL provides hull algorithms in 2-d and arbitrary dimensions with exact-predicates kernels[8](https://docs.scipy.org/doc/scipy/reference/spatial.html) • [9](https://doc.cgal.org/latest/Manual/tutorial_hello_world.html) |
## Definition and basic structure
A set is convex if, for any two points p and q in it, the whole line segment from p to q also lies in it. The convex hull of a set S is the smallest convex set containing S, and for a finite point set P it is a [convex polytope](https://www.edgepedia.org/convex-polytope) with vertices drawn from P. A point of P that is a vertex of the hull is called an extreme point, and a set consisting only of extreme points is strongly convex[1](https://doc.cgal.org/Manual/3.1/doc_html/cgal_manual/Convex_hull_d/Chapter_main.html).
The hull can be described in two dual ways: as the convex hull of the vertex set of a polytope, or as the intersection of the halfspaces inducing its facets[10](https://www.sciencedirect.com/science/article/pii/S0925772196000235). A finite hull is a polytope, and Carathéodory's theorem bounds how much of the point set is needed to describe any interior point: in \( \mathbb{R}^d \), every point of \( \operatorname{conv}(T) \) is a convex combination of at most \( d+1 \) points of T, so in the plane three points always suffice[4](https://elliotpaquette.github.io/high-dimensional-probability/lectures/02-convex-hulls.html).
## Planar algorithms
Ronald L. Graham's 1972 paper, "An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set," gave the first \( O(n \log n) \) planar hull algorithm[5](https://dblp.org/rec/journals/ipl/Graham72.html). Graham's scan sorts the points by angle around an interior point and then removes points that would create a right turn while scanning; the turn test is done with orientation predicates rather than trigonometry[11](https://farzadhallaji.github.io/CompGeoLectures/03_Convex_Hulls/03_grahams_scan/).
A. M. Andrew's 1979 variant, often called the monotone chain algorithm, sorts points by x-coordinate instead and builds the lower and upper hulls as x-monotone chains, whose concatenation is the hull[12](https://www.sciencedirect.com/science/article/abs/pii/0020019079900723). CGAL's ch_graham_andrew implements this variant with \( O(n \log n) \) worst-case time[13](https://doc.cgal.org/Manual/latest/doc_html/cgal_manual/Convex_hull_2_ref/Function_ch_graham_andrew.html).
Other classical algorithms trade simplicity against output size. Jarvis's gift-wrapping march and Eddy's algorithm, the two-dimensional ancestor of Quickhull, both run in \( O(nh) \), where h is the number of extreme points[14](https://doc.cgal.org/Manual/latest/doc_html/cgal_manual/Convex_hull_2/Chapter_main.html). In the output-sensitive model, Kirkpatrick and Seidel (1986) and Chan (1996) reached \( O(n \log h) \), which is optimal in that model[6](https://arxiv.org/abs/1810.00455). When input arrives as a stream that cannot be stored, the problem changes character: no single-pass streaming algorithm can compute the planar hull in \( o(n) \) space, because the problem is at least as hard as sorting[6](https://arxiv.org/abs/1810.00455).
## Quickhull and higher dimensions
The Quickhull algorithm of C. Bradford Barber, David P. Dobkin, and Hannu Huhdanpaa, published in ACM Transactions on Mathematical Software in 1996, combines the two-dimensional Quickhull method with the general-dimension Beneath-Beyond algorithm, an incremental scheme that adds each point by locating the visible facets, building a cone of new facets to the horizon ridges, and deleting the visible facets[3](https://cise.ufl.edu/~ungor/courses/fall06/papers/QuickHull.pdf). Unlike randomized incremental algorithms, Quickhull processes the furthest point of each outside set first, which makes it faster when the input contains many non-extreme points and uses less memory, since it discards old facets rather than retaining them in a hierarchy[3](https://cise.ufl.edu/~ungor/courses/fall06/papers/QuickHull.pdf).
Its practical performance depends on dimension through the output size. With n input points, v output vertices, and \( f_v \) the maximum number of facets of a hull with v vertices, [Qhull](https://www.edgepedia.org/qhull) runs in \( O(n \log v) \) in 2-d and 3-d and \( O(n f_v / v) \) otherwise, where \( f_v = O(v^{\lfloor d/2 \rfloor} / \lfloor d/2 \rfloor!) \) grows rapidly with dimension[15](https://www.qhull.org/html/qh-code.htm). This is why exact hull computation is tractable in low dimensions and expensive in high ones[16](https://technav.ieee.org/topic/convex-hulls/).
The Barber, Dobkin, and Huhdanpaa paper conjectured that Quickhull runs in worst-case time \( O(n \log h) \) when the input points have limited precision. Michael T. Goodrich, a computer scientist at the [University of California, Irvine](https://www.edgepedia.org/university-of-california-irvine), disproved this in 2025 with an explicit construction of n points of bounded precision for which the hull has h vertices but Quickhull takes quadratic time[17](https://www.sciencedirect.com/science/article/pii/S002001902500002X).
## Floating-point robustness
Hull algorithms assume well-behaved input, and floating-point arithmetic breaks that assumption: roundoff can turn a small positive orientation value into a small negative one, producing concave facets, flipped facets, or duplicated faces. Qhull addresses this in two ways. By default it merges facets, using option 'C-0' in 2-d through 4-d and 'Qx' in 5-d and higher; empirically the merged output stays within about 30 times the maximum roundoff error of a distance computation of the exact hull. The alternative, option 'QJ', joggles the input by adding a small random quantity to each coordinate, restarting with a larger joggle after a failure; this is simpler but about 2,000 times less accurate, and it even constructs a hull when all input points are identical[7](https://www.qhull.org/html/qh-impre.htm) • [18](https://www.qhull.org/html/index.htm).
A different route to robustness is exact arithmetic. CGAL's convex hull code needs only coordinate comparisons and orientation tests on the input points, so a kernel with exact predicates but inexact constructions suffices, combining floating-point speed with guaranteed correct decisions[9](https://doc.cgal.org/latest/Manual/tutorial_hello_world.html).
## Related problems and applications
Several standard constructions reduce to convex hulls. A [Delaunay triangulation](https://www.edgepedia.org/delaunay-triangulation) in \( \mathbb{R}^d \) is obtained by lifting the points onto a paraboloid in one higher dimension and taking the lower convex hull; the nearest-site Delaunay triangulation is the projection of the lower hull and the furthest-site triangulation the projection of the upper hull[3](https://cise.ufl.edu/~ungor/courses/fall06/papers/QuickHull.pdf) • [1](https://doc.cgal.org/Manual/3.1/doc_html/cgal_manual/Convex_hull_d/Chapter_main.html). Halfspace intersection is equivalent to a hull in dual space[3](https://cise.ufl.edu/~ungor/courses/fall06/papers/QuickHull.pdf).
In physics engines and motion planners, collision detection between convex shapes is handled by the Gilbert-Johnson-Keerthi algorithm, which recent work recasts as a sub-case of the Frank-Wolfe method in convex optimization[19](https://arxiv.org/abs/2205.09663). In geographic information systems, PostGIS's ST_ConvexHull returns the smallest convex geometry enclosing its input, a Polygon in the general case, a two-point LineString for collinear points, and a Point for identical points; it is commonly used to outline the area affected by a set of point observations[2](https://postgis.net/docs/manual-3.7/en/ST_ConvexHull.html). Within mathematical programming, if one takes the convex hull of the integer-feasible points of a mixed-integer program, one obtains the polyhedron for which the linear relaxation is tight, and cutting-plane methods seek to approximate this hull a single inequality at a time.[16](https://technav.ieee.org/topic/convex-hulls/)
## Software
Qhull, the implementation of Quickhull, is the engine behind SciPy's scipy.spatial.ConvexHull class, which exposes hull simplices, facet-neighbor structure, and the hyperplane equation of each facet[8](https://docs.scipy.org/doc/scipy/reference/spatial.html). CGAL offers 2-d hull and extreme-point functions parameterized by a traits class defining the needed predicates, several algorithms with different running times, and a d-dimensional hull class supporting incremental construction[14](https://doc.cgal.org/Manual/latest/doc_html/cgal_manual/Convex_hull_2/Chapter_main.html) • [1](https://doc.cgal.org/Manual/3.1/doc_html/cgal_manual/Convex_hull_d/Chapter_main.html). Recent CGAL releases added hull intersection tests in 3-d and sped up high-dimensional hull computation[20](https://www.cgal.org/2026/06/11/cgal62/).
## References
1. [dD Convex Hulls and Delaunay Triangulations, CGAL Manual (Susan Hert and Michael Seel)](https://doc.cgal.org/Manual/3.1/doc_html/cgal_manual/Convex_hull_d/Chapter_main.html)
2. [ST_ConvexHull, PostGIS 3.7 Manual](https://postgis.net/docs/manual-3.7/en/ST_ConvexHull.html)
3. [C. Bradford Barber, David P. Dobkin, Hannu Huhdanpaa (1996). The Quickhull Algorithm for Convex Hulls. ACM Transactions on Mathematical Software 22(4):469-483.](https://cise.ufl.edu/~ungor/courses/fall06/papers/QuickHull.pdf)
4. [Lecture 2: Convex Hulls and Sparse Approximation, High-Dimensional Probability (Elliot Paquette)](https://elliotpaquette.github.io/high-dimensional-probability/lectures/02-convex-hulls.html)
5. [Ronald L. Graham (1972). An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set. dblp record.](https://dblp.org/rec/journals/ipl/Graham72.html)
6. [Martin Farach-Colton, Meng Li, Meng-Tsung Tsai (2018). Streaming Algorithms for Planar Convex Hulls. arXiv:1810.00455.](https://arxiv.org/abs/1810.00455)
7. [Imprecision in Qhull, Qhull manual (C. B. Barber)](https://www.qhull.org/html/qh-impre.htm)
8. [Spatial algorithms and data structures (scipy.spatial), SciPy v1.18.0 Manual](https://docs.scipy.org/doc/scipy/reference/spatial.html)
9. [CGAL 6.2 Manual: Hello World, CGAL Editorial Board](https://doc.cgal.org/latest/Manual/tutorial_hello_world.html)
10. [How good are convex hull algorithms? Discrete & Computational Geometry 7 (1997)](https://www.sciencedirect.com/science/article/pii/S0925772196000235)
11. [Graham's Scan, Computational Geometry Notes (Farzad Hallaji)](https://farzadhallaji.github.io/CompGeoLectures/03_Convex_Hulls/03_grahams_scan/)
12. [A. M. Andrew (1979). Another efficient algorithm for convex hulls in two dimensions. Information Processing Letters 9(5):216-219.](https://www.sciencedirect.com/science/article/abs/pii/0020019079900723)
13. [CGAL::ch_graham_andrew, CGAL Reference Manual](https://doc.cgal.org/Manual/latest/doc_html/cgal_manual/Convex_hull_2_ref/Function_ch_graham_andrew.html)
14. [2D Convex Hulls and Extreme Points, CGAL User Manual](https://doc.cgal.org/Manual/latest/doc_html/cgal_manual/Convex_hull_2/Chapter_main.html)
15. [Qhull code, Qhull manual (performance section)](https://www.qhull.org/html/qh-code.htm)
16. [Convex hulls, IEEE Technology Navigator](https://technav.ieee.org/topic/convex-hulls/)
17. [Michael T. Goodrich (2025). A lower bound for the Quickhull convex hull algorithm that disproves the Quickhull precision conjecture. Information Processing Letters 189.](https://www.sciencedirect.com/science/article/pii/S002001902500002X)
18. [Qhull manual (precision limitations and joggled input)](https://www.qhull.org/html/index.htm)
19. [Collision Detection Accelerated: An Optimization Perspective. arXiv:2205.09663.](https://arxiv.org/abs/2205.09663)
20. [CGAL 6.2 released, CGAL project news](https://www.cgal.org/2026/06/11/cgal62/)
---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Geometry and topology › Metric, convex, and discrete geometry*
*Initially written Sep 17, 2026 · Reviewed: Sep 30, 2026; Oct 15, 2026 · Edited: Sep 30, 2026; Oct 15, 2026 · Last review: Oct 15, 2026*
*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*
License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license