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).
More things to try:
