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