TOPICS
Search

Convex Hull

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
ConvexHull2D
ConvexHull3D

The convex hull of a set of points S in n dimensions is the intersection of all convex sets containing S. For N points p_1, ..., p_N, the convex hull C is then given by the expression

C={sum_(j=1)^Nlambda_jp_j:lambda_j>=0 for all j and sum_(j=1)^Nlambda_j=1}.

Computing the convex hull is a problem in computational geometry. The indices of the points specifying the convex hull of a set of points in two dimensions is given by the command ConvexHull[pts] in the Wolfram Language package ComputationalGeometry` . Future versions of the Wolfram Language will support three-dimensional convex hulls. A makeshift package for computing three-dimensional convex hulls in the Wolfram Language has been written by Meeussen and Weisstein.

In d dimensions, the "gift wrapping" algorithm, which has complexity O(n^(|_d/2_|+1)), where |_x_| is the floor function, can be used (Skiena 1997, p. 352). In two and three dimensions, however, specialized algorithms exist with complexity O(nlnn) (Skiena 1997, pp. 351-352). Yao (1981) has proved that any decision-tree algorithm for the two-dimensional case requires quadratic or higher-order tests, and that any algorithm using quadratic tests (which includes all currently known algorithms) cannot be done with lower complexity than O(nlnn). However, it remains an open problem whether better complexity can be obtained using higher-order polynomial tests (Yao 1981). Yao's analysis applies to the hardest cases, where the number of vertices n is equal to the number of vertices in the hull h. In easier cases where h<n, the bound of O(nlnn) can be improved to O(nlnh) (Chan 1996).

O'Rourke (1998) gives a robust two-dimensional implementation as well as an O(n^2) three-dimensional implementation. Qhull works efficiently in 2 to 8 dimensions (Barber et al. 1996).

The dual polyhedron of any non-convex uniform polyhedron is a stellated form of the convex hull of the given polyhedron (Wenninger 1983, pp. 3-4 and 40).

See also

Carathéodory's Fundamental Theorem, Computational Geometry, Cross Polytope, Delaunay Triangulation, Expansion, Geometric Span, Groemer Packing, Groemer Theorem, Happy End Problem, Radon's Theorem, Sausage Conjecture, Sylvester's Four-Point Problem, Temperature, Voronoi Diagram Explore this topic in the MathWorld classroom

Explore with Wolfram|Alpha

References

Barber, C. B.; Dobkin, D. P.; and Huhdanpaa, H. T. "The Quickhull Algorithm for Convex Hulls." ACM Trans. Mathematical Software 22, 469-483, 1996.Chan, T. "Optimal Output-sensitive Convex Hull Algorithms in Two and Three Dimensions." Disc. Comput. Geom. 16, 361-368, 1996. http://www.cs.uwaterloo.ca/~tmchan/pub.html#conv23d.Croft, H. T.; Falconer, K. J.; and Guy, R. K. Unsolved Problems in Geometry. New York: Springer-Verlag, p. 8, 1991.de Berg, M.; van Kreveld, M.; Overmans, M.; and Schwarzkopf, O. "Convex Hulls: Mixing Things." Ch. 11 in Computational Geometry: Algorithms and Applications, 2nd rev. ed. Berlin: Springer-Verlag, pp. 235-250, 2000.Edelsbrunner, H. and Mücke, E. P. "Three-Dimensional Alpha Shapes." ACM Trans. Graphics 13, 43-72, 1994.The Geometry Center. "Qhull." http://www.qhull.org/. Meeussen, W. L. J. and Weisstein, E. W. "Convex Hull." Mathematica package ConvexHull.m.O'Rourke, J. Computational Geometry in C, 2nd ed. Cambridge, England: Cambridge University Press, 1998.Preparata, F. R. and Shamos, M. I. Computational Geometry: An Introduction. New York: Springer-Verlag, 1985.Santaló, L. A. Integral Geometry and Geometric Probability. Reading, MA: Addison-Wesley, 1976.Seidel, R. "Convex Hull Computations." Ch. 19 in Handbook of Discrete and Computational Geometry (Ed. J. E. Goodman and J. O'Rourke). Boca Raton, FL: CRC Press, pp. 361-375, 1997.Skiena, S. S. "Convex Hull." §8.6.2 in The Algorithm Design Manual. New York: Springer-Verlag, pp. 351-354, 1997.Wenninger, M. J. Dual Models. Cambridge, England: Cambridge University Press, 1983.Yao, A. C.-C. "A Lower Bound to Finding Convex Hulls." J. ACM 28, 780-787, 1981.

Referenced on Wolfram|Alpha

Convex Hull

Cite this as:

Weisstein, Eric W. "Convex Hull." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ConvexHull.html

Subject classifications