Representing a convex hull in higher dimensions (3+)

Question

In 2d a convex hull is represented as basically a tour of points. Seems like this representation might fall apart beyond 2 dimensions. Since, I'm going to be working with them soon, I'd like to know ahead of time what the "standard" is for doing so, if there is one for doing so, as the hulls may be used by others.

Clarification: The standard I was referring to was in terms of output formats, such that from that output, a program could make use of the hull for other things.

Answer 1

A collection of points is always enough to specify any hull completely, but working out the connectivity of the points will often require, in practice, running the hull algorithm again.

EDIT: If you need edge or face data, you get this for free during algorithms such as quickhull. I will assume N dimensions. Basically, one is constantly finding planes defined by N points, with an associated normal vector. If there are still points on the side of the plane given by the normal vector, you create new planes defined by the point furthest away and remove any on the wrong side of the new set of planes. These planes define (N-1)-cells (in 3D these are faces, in 2D these are edges) and give the highest dimensional representation of the hull at this point in the algorithm. The algorithm continues until there are no planes with points on the wrong side. The final planes give the (N-1)-cells of the final hull, for which their defining points are vertices. There is an issue concerning planes that can be defined by more than N points but there are a number of ways in which one can deal with them, see http://www.qhull.org/ uses a number of strategies, the most obvious of which is using a Delaunay triangulation (which you have code for once you have a convex hull algorithm).

In two dimensions you have a list of points and some edges. You can order them to make a tour if you wish. You need both the edges and the points for any hull.

In 3D you need points and and edges, or faces and edges, or points and faces as a minimal representation. But it might be efficient to have all three sometimes. Maybe you want to represent faces in terms of the edges they are made of, maybe the points, maybe both. It is a trade off between memory and time or accessibility.

You have the same thing in higher dimensions, but with cells (3D+ faces) as well as faces, edges and points. With higher dimensions the space needed to store the cell data can become quite large, so a collection of points and edges can become desirable, you can see evidence of this pattern here: http://en.wikipedia.org/wiki/Hypercube#Elements .

Then you have a choice about how the higher dimensional cells are represented, to they reference points, edges, faces, lower dimensional cells, higher dimensional cells. The question is: you keep track of every relationship between different dimensional cells (like the relationship between faces and edges, but higher dimensional)? or the number of the types of these relationships will increase superlinearly, it is an additional combinatoral as will the number relationships of each type to be represented. So do you throw it all away and calculate it on the fly. The space and time requirements for even moderate sized problems can become significant - so the choice of representation really depends on what you are doing.

Personally, I usually use a collection of points with edges that reference them.

ND geometry: http://en.wikipedia.org/wiki/Polytope