The convex hull of a set of points in dimensions is the intersection of all convex sets containing . For points , ..., , the convex hull is then given by the expression
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 dimensions, the "gift wrapping" algorithm, which has complexity , where is the floor function, can be used (Skiena 1997, p. 352). In two and three dimensions, however, specialized algorithms exist with complexity (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 . 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 is equal to the number of vertices in the hull . In easier cases where , the bound of can be improved to (Chan 1996).
O'Rourke (1998) gives a robust two-dimensional implementation as well as an 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).
Barber, C. B.; Dobkin, D. P.; and Huhdanpaa, H. T. "The Quickhull Algorithm for Convex Hulls." ACM Trans. Mathematical Software22, 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. Graphics13, 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. ACM28, 780-787, 1981.
in 
dimensions is the intersection of all convex sets containing 
. For 
points 
, ..., 
, the convex hull 
is then given by the expression 
dimensions, the "gift wrapping" algorithm, which has complexity 
, where 
is the floor function, can be used (Skiena 1997, p. 352). In two and three dimensions, however, specialized algorithms exist with complexity 
(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 
. 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 
is equal to the number of vertices in the hull 
. In easier cases where 
, the bound of 
can be improved to 
(Chan 1996). 
three-dimensional implementation. Qhull works efficiently in 2 to 8 dimensions (Barber et al. 1996). 
Meeussen, W. L. J. and Weisstein, E. W. "Convex Hull." Mathematica package