Higher Dimensions
A number of algorithms are known for the three-dimensional case, as well as for arbitrary dimensions. See http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html. See also David Mount's Lecture Notes for comparison. Refer to Lecture 4 for the latest developments, including Chan's algorithm.
For a finite set of points, the convex hull is a convex polyhedron in three dimensions, or in general a convex polytope for any number of dimensions, whose vertices are some of the points in the input set. Its representation is not so simple as in the planar case, however. In higher dimensions, even if the vertices of a convex polytope are known, construction of its faces is a non-trivial task, as is the dual problem of constructing the vertices given the faces. The size of the output may be exponentially larger than the size of the input, and even in cases where the input and output are both of comparable size the known algorithms for high-dimensional convex hulls are not output-sensitive due both to issues with degenerate inputs and with intermediate results of high complexity.
Read more about this topic: Convex Hull Algorithms
Famous quotes containing the words higher and/or dimensions:
“This might be the end of the world. If Joe lost we were back in slavery and beyond help. It would all be true, the accusations that we were lower types of human beings. Only a little higher than apes. True that we were stupid and ugly and lazy and dirty and, unlucky and worst of all, that God Himself hated us and ordained us to be hewers of wood and drawers of water, forever and ever, world without end.”
—Maya Angelou (b. 1928)
“The truth is that a Pigmy and a Patagonian, a Mouse and a Mammoth, derive their dimensions from the same nutritive juices.... [A]ll the manna of heaven would never raise the Mouse to the bulk of the Mammoth.”
—Thomas Jefferson (1743–1826)