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:
“We are conscious of an animal in us, which awakens in proportion as our higher nature slumbers. It is reptile and sensual, and perhaps cannot be wholly expelled; like the worms which, even in life and health, occupy our bodies. Possibly we may withdraw from it, but never change its nature. I fear that it may enjoy a certain health of its own; that we may be well, yet not pure.”
—Henry David Thoreau (1817–1862)
“Is it true or false that Belfast is north of London? That the galaxy is the shape of a fried egg? That Beethoven was a drunkard? That Wellington won the battle of Waterloo? There are various degrees and dimensions of success in making statements: the statements fit the facts always more or less loosely, in different ways on different occasions for different intents and purposes.”
—J.L. (John Langshaw)