Convex Hull
 |
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 Mathematica package ComputationalGeometry` . Future versions of Mathematica will support three-dimensional convex hulls. A makeshift package for computing three-dimensional convex hulls in Mathematica 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 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.
Weisstein, Eric W. "Convex Hull." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/ConvexHull.html
Contact the MathWorld Team
triangle interior
