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:
“For human nature, being more highly pitched, selved, and distinctive than anything in the world, can have been developed, evolved, condensed, from the vastness of the world not anyhow or by the working of common powers but only by one of finer or higher pitch and determination than itself.”
—Gerard Manley Hopkins (1844–1889)
“I was surprised by Joe’s asking me how far it was to the Moosehorn. He was pretty well acquainted with this stream, but he had noticed that I was curious about distances, and had several maps. He and Indians generally, with whom I have talked, are not able to describe dimensions or distances in our measures with any accuracy. He could tell, perhaps, at what time we should arrive, but not how far it was.”
—Henry David Thoreau (1817–1862)